Zdefiniuj funkcję f (n) dla dodatniej liczby całkowitej n w następujący sposób:

• n / 2 , jeśli n jest parzyste
• 3 * n + 1 , jeśli n jest nieparzyste

Jeśli wielokrotnie zastosujesz tę funkcję do dowolnego n większego niż 0, wynik zawsze wydaje się zbieżny do 1 (chociaż nikt nie był jeszcze w stanie tego udowodnić). Ta właściwość jest znana jako hipoteza Collatza .

Zdefiniuj czas zatrzymania liczby całkowitej jako liczbę przypadków, w których musisz przejść przez funkcję Collatz f, zanim osiągnie 1. Oto czasy zatrzymania pierwszych 15 liczb całkowitych:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Zadzwońmy do dowolnego zestawu numerów o tym samym czasie zatrzymania kuzyni Collatz . Na przykład 5 i 32 są kuzynami Collatz, z czasem zatrzymania wynoszącym 5.

Twoje zadanie: napisanie programu lub funkcji, która przyjmuje nieujemną liczbę całkowitą i generuje zestaw kuzynów Collatz, których czas zatrzymania jest równy tej liczbie całkowitej.

Wkład

Nieujemna liczba całkowita S, podana przez STDIN, ARGV lub argument funkcji.

Wydajność

Lista wszystkich liczb, których czas zatrzymania wynosi S, posortowanych w porządku rosnącym . Lista może być wyprowadzana przez twój program lub zwracana lub wyprowadzana przez twoją funkcję. Format wyjściowy jest elastyczny: separacja spacji, separacja nowego wiersza lub dowolny standardowy format listy twojego języka jest w porządku, pod warunkiem, że liczby są łatwe do odróżnienia od siebie.

Wymagania

Twoje zgłoszenie musi dawać prawidłowe wyniki dla dowolnego S ≤ 30. Powinno ono zakończyć się w ciągu sekund lub minut, a nie godzin lub dni.

Przykłady

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Oto streszczenie wyniku dla S = 30 .

To jest golf-golf : wygrywa najkrótszy program w bajtach. Powodzenia!

Pyth, 26 24 21 bajtów

Su+yMG-/R3fq4%T6G1Q]1

Ten kod uruchamia się natychmiast dla S=30. Wypróbuj sam: demonstracja

Dzięki @isaacg za zapisanie 5 bajtów.

Wyjaśnienie

Mój kod zaczyna się od 1i cofam funkcję Collatz. Mapy to wszystkie numery dz S-1krokiem do 2*di (d-1)/3. Ten ostatni nie zawsze jest ważny.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print

Mathematica, 98 92 89 bajtów

To rozwiązanie rozwiązuje S = 30natychmiast:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

Jest to funkcja bez nazwy, która przyjmuje Sza swój jedyny parametr i zwraca listę kuzynów Collatz.

Algorytm jest prostym, szerokim wyszukiwaniem. Kuzyni Collatz dla danej Ssą wszystkie liczby całkowite, które można dojechać z kuzynów Collatz za S-1pośrednictwem 2*nlub liczb nieparzystych, które mogą być osiągnięte poprzez (n-1)/3. Musimy również upewnić się, że produkujemy tylko te liczby całkowite, które zostały osiągnięte po raz pierwszy po Skrokach, więc śledzimy wszystkich poprzednich kuzynów pi usuwamy je z wyniku. Ponieważ i tak to robimy, możemy zaoszczędzić kilka bajtów, obliczając kroki wszystkich poprzednich kuzynów (nie tylko tych z S-1), aby zaoszczędzić kilka bajtów (co czyni to nieco wolniejszym, ale nie zauważalnie wymaganym S).

Oto nieco bardziej czytelna wersja:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &

Python 2, 86 83 75 73 71 bajtów

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Zadzwoń jak f(30). n = 30jest prawie natychmiastowy.

(Dzięki @DLosc za pomysł rekurencji, kponieważ jest liczbą, a nie listą kuzynów i kilkoma bajtami. Dziękuję @isaacg za upuszczenie ~-.)

Ten wariant jest znacznie krótszy, ale niestety trwa zbyt długo z powodu wykładniczego rozgałęzienia:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))

CJam, 29 26 bajtów

Xari{{2*_Cmd8=*2*)}%1-}*$p

Podziękowania dla @isaacg za pomysł usunięcia 1 po każdej iteracji, co pozwoliło mi zaoszczędzić dwa bajty bezpośrednio, a drugi pośrednio.

Wypróbuj online w interpretatorze CJam (powinien zakończyć się w niecałą sekundę).

Jak to działa

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))

CJam, 35 bajtów

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Wyjaśnienie już wkrótce. Jest to wersja znacznie szybsza niż podejście „dość proste” (zobacz w historii edycji).

Wypróbuj online tutaj, ponieważ N = 30działa w kilka sekund w wersji online i natychmiast w kompilatorze Java

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Gdy xjest 30, program trwa 15 minut i 29 sekund.

Rozszerzony

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}

Python 2, 118 bajtów

Pomyślałem, że nie osiągnęłbym najlepszego wyniku w Pythonie po obejrzeniu rozwiązania @ Sp3000. Ale wyglądało to na zabawny mały problem, więc i tak chciałem wypróbować niezależne rozwiązanie:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

To samo przed usunięciem białych znaków:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Jest to bardzo bezpośrednia implementacja szerokiego pierwszego wyszukiwania. Na każdym kroku mamy zestaw z czasem zatrzymania k, i uzyskujemy zestaw z czasem zatrzymania k + 1, dodając możliwych poprzedników każdej wartości tw zestawie z kroku k:

• 2 * t jest zawsze możliwym poprzednikiem.
• Jeśli tmożna zapisać jako 3 * u + 1, gdzie ujest liczbą nieparzystą, która nie jest 1, to ujest również poprzednikiem.

Uruchomienie N = 30mojego MacBooka Pro zajmuje około 0,02 sekundy .

PHP 5.4+, 178 bajtów

Funkcja

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Test i wyjście

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) działa w 0,24 sekundy * , zwraca 732 elementy. Kilka jest

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Aby zaoszczędzić na bajtach, musiałem dodawać ksorti array_keysna każdym kroku. Jedynym innym wyborem, jaki miałem, było wykonanie małej funkcji otoki, która wywołuje, c()a następnie wywołuje array_keysi ksortraz wynik. Ale ponieważ czas wciąż był przyzwoity, postanowiłem wziąć hit za niską liczbę bajtów. Bez właściwego sortowania i przetwarzania dla S (30) czas wynosi średnio 0,07 sekundy .

Jeśli ktoś ma jakieś sprytne sposoby uzyskania poprawnego przetwarzania tylko raz bez zbyt wielu dodatkowych bajtów, daj mi znać! (Przechowuję moje liczby jako klucze tablicy, stąd użycie array_keysiksort )

Język C.

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}