Dzisiaj przyjrzymy się sekwencji a związanej z funkcją Collatz f :

Nazywamy sekwencję formie oo, F (z), F (F (z)) ... w sekwencji Collatz .

Pierwsza liczba w naszej sekwencji, a (1) , to 0 . Przy wielokrotnym stosowaniu f wpada w cykl 0 → 0 →…

Najmniejsza liczba, której jeszcze nie widzieliśmy, to 1, co daje (2) = 1 . Przy wielokrotnym stosowaniu f , przechodzi on w cykl 1 → 4 → 2 → 1 →…

Teraz widzieliśmy liczbę 2 w powyższym cyklu, więc następną najmniejszą liczbą jest a (3) = 3 , mieszcząca się w cyklu 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 →…

We wszystkich powyższych cyklach widzieliśmy już 4 i 5 , więc następna liczba to (4) = 6 .

Do tej pory powinieneś mieć pomysł. a (n) jest najmniejszą liczbą, która nie była częścią żadnej sekwencji Collatz dla wszystkich a (1),…, a (n - 1) .

Napisz program lub funkcję, która przy dodatniej liczbie całkowitej n zwraca a (n) . Najkrótszy kod w bajtach wygrywa.

Przypadki testowe:

1  -> 0
2  -> 1
3  -> 3
4  -> 6
5  -> 7
6  -> 9
7  -> 12
8  -> 15
9  -> 18
10 -> 19
50 -> 114

(Jest to sekwencja OEIS A061641 .)

Galaretka , 20 19 bajtów

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ
Ç¡Ṫ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Ç¡Ṫ              Main link. No explicit arguments. Default argument: 0
 ¡               Read an integer n from STDIN and do the following n times.
Ç                  Call the helper link.
  Ṫ              Tail; extract the last element of the resulting array.


ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ  Helper link. Argument: A (array)

  J              Yield all 1-based indices of A, i.e., [1, ..., len(A)]. Since 0
                 belongs to A, there is at least one index that does belong to A.
ḟ@               Filter-false swapped; remove all indices that belong to A.
   Ḣ             Head; extract the first index (i) that hasn't been removed.
           ÐĿ    Call the quicklink to the left on i, then until the results are no
                 longer unique. Collect all unique results in an array.
         Ḃ?      If the last bit of the return value (r) is 1:
       $           Apply the monadic 3-link chain to the left to r.
    ×3‘              Yield 3r + 1.
        H        Else, halve r.
              Ṛ  Yield A, reversed.
             ;   Concatenate the results array with reversed A.

Po n iteracjach wartość a (n + 1) będzie na początku tablicy. Ponieważ łączymy nową tablicę z odwróconą kopią starej, oznacza to, że na końcu znajdzie się (n) .

Haskell, 93 92 bajty

c x|x<2=[[0,2]!!x]|odd x=x:c(3*x+1)|1<2=x:c(div x 2)
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!)

Przykład użycia: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10-> 19.

c xto cykl Collatz xz odrobiną oszukiwania x == 1. Główne funkcje pętli przez wszystkie liczby całkowite i utrzymuje te, które nie są c xdla xw [0..y-1]. Niemal bezpośrednie wdrożenie definicji. Ponieważ operator indeksu Haskell !!jest oparty na 0, zaczynam -1od dodania (w przeciwnym razie bezużytecznego) numeru, aby naprawić indeks.

MATL , 46 40 bajtów

Oiq:"tX>Q:yX-X<`t0)to?3*Q}2/]h5M1>]Pv]0)

Wypróbuj online!

Wyjaśnienie

Kod ma zewnętrzną forpętlę, która generuje nsekwencje Collatz, po jednej w każdej iteracji. Każda sekwencja jest generowana przez wewnętrzną do...whilepętlę, która oblicza nowe wartości i przechowuje je w wektorze sekwencji, aż do uzyskania a 1lub 0. Po zakończeniu sekwencji wektor jest odwracany i łączony z wektorem globalnym, który zawiera wartości ze wszystkich poprzednich sekwencji. Ten wektor może zawierać powtarzające się wartości. Odwrócenie wektora sekwencji zapewnia, że ​​na końcu zewnętrznej pętli pożądany wynik (wartość początkowa ostatniej sekwencji) będzie na końcu wektora globalnego.

Pseudokod :

1  Initiallization
2  Generate n sequences (for loop):
3    Compute initial value for the k-th sequence
4    Generate the k-th sequence (do...while loop)
5      Starting from latest value so far, apply the Collatz algorithm to get next value
6      Update sequence with new value 
7      Check if we are done. If so, exit loop. We have the k-th sequence
8    Update vector of seen values
9  We now have the n sequences. Get final result

Skomentowany kod :

O           % Push 0                                                          1
iq:         % Input n. Generate [1 2 ... n-1]                                 ·
"           % For loop: repeat n-1 times. Let k denote each iteration         2
  t         %   Duplicate vector of all seen values                           · 3
  X>Q       %   Take maximum, add 1                                           · ·
  :         %   Range from 1 to that: these are potential initial values      · ·
  y         %   Duplicate vector of all seen values                           · ·
  X-X<      %   Set difference, minimum: first value not seen                 · ·
  `         %   Do...while: this generates the k-th Collatz sequence          · 4
    t0)     %     Duplicate, push last value of the sequence so far           · · 5
    to      %     Duplicate, parity: 1 if odd, 0 if even                      · · ·
    ?       %     If odd                                                      · · ·
      3*Q   %       Times 3, plus 1                                           · · ·
    }       %     Else                                                        · · ·
      2/    %       Half                                                      · · ·
    ]       %     End if                                                      · · ·
    h       %     Concatenate new value of the sequence                       · · 6
    5M      %     Push the new value again                                    · · 7
    1>      %     Does it exceed 1? This is the loop condition                · · ·
  ]         %   End do...while. The loops ends when we have reached 0 or 1    · ·
  P         %   Reverse the k-th Collatz sequence                             · 8
  v         %   Concatenate with vector of previously seen values             · ·
]           % End for                                                         ·
0)          % Take last value. Implicitly display.                            9

Brachylog , 70 67 65 63 62 bajtów

,[]:?:1ih.
,0<=X=,?'eXg{t{:2/.*?|:3*+.}gB,(?.sB;?:Bc:2&.)}:?c.

Wypróbuj online!

Python 2, 97 96 bajtów

r,=s={-1}
exec'n=r=min({r+1,r+2,r+3}-s)\nwhile{n}-s:s|={n};n=(n/2,3*n+1)[n%2]\n'*input()
print r

Wykorzystuje fakt, że wszystkie wielokrotności 3 są czyste. Przetestuj na Ideone .

Jak to działa

W pierwszym wierszu r,=s={-1}ustawia s = {-1} (zestaw) i r = -1 .

Następnie odczytujemy liczbę całkowitą ze STDIN, powtarzamy pewien ciąg znaków wiele razy, a następnie go wykonujemy. Jest to równoważne z następującym kodem Python.

for _ in range(input())
    n=r=min({r+1,r+2,r+3}-s)
    while{n}-s:
        s|={n}
        n=(n/2,3*n+1)[n%2]

W każdej iteracji zaczynamy od znalezienia najmniejszego elementu {r + 1, r + 2, r + 3} , który nie należy do s . W pierwszej iteracji inicjuje r jako 0 .

We wszystkich kolejnych seriach s może (i będzie) zawierać niektóre z r + 1 , r + 2 i r + 3 , ale nigdy nie wszystkie, ponieważ wszystkie wielokrotności 3 są czyste. Aby zweryfikować to stwierdzenie, że nie obserwujemy wielokrotność m od 3 jest postaci 3k + 1 . To pozostawia 2m jako jedyny możliwy obraz wstępny, który jest również wielokrotnością 3 . Zatem m nie może pojawić się w sekwencji Collatz dowolnej liczby, która jest mniejsza niż m , a zatem jest czysta.

Po zidentyfikowaniu ri zainicjowaniu n , stosujemy funkcję Collatz za pomocą n=(n/2,3*n+1)[n%2], dodając każdą wartość pośrednią n do zbioru s za pomocą s|={n}. Gdy napotkamy liczbę n, która jest już w s , {n}-sda pusty zestaw, a iteracja się zatrzyma.

Ostatnia wartość r jest pożądanym elementem sekwencji.

Pyth , 32 bajty

VtQ=+Y.u?%N2h*3N/N2Z)=Zf!}TYhZ)Z

Zestaw testowy.

Java, 148 bajtów

int a(int n){if(n<2)return 0;int f=a(n-1),b,i,c;do{f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}while(b<1);return f;}

Ideone to! (Ostrzeżenie: złożoność wykładnicza z powodu optymalizacji zerowej).

Przekształcenie go z do...whilepętli w forpętlę byłoby bardziej golfowe, ale mam z tym problem.

Porady w golfa są jak zwykle mile widziane.

Perl6, 96

my @s;my $a=0;map {while ($a=@s[$a]=$a%2??3*$a+1!!$a/2)>1 {};while @s[++$a] {}},2..slurp;$a.say;

Na podstawie odpowiedzi Perla 5 . Trochę dłużej, ponieważ składnia Perl6 jest mniej wybaczająca niż składnia Perl5, ale na razie się z tym pogodzę.

PHP, 233 124 bajty

<?$n=$argv[1];for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}echo$v;

+4 dla funkcji:

function a($n){for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}return$v;}

Perl 5-74 bajtów

map{0 while 1<($a=$c[$a]=$a%2?$a*3+1:$a/2);0 while$c[++$a]}2..<>;print$a+0

To dość proste rozwiązanie. Wielokrotnie stosuje funkcję Collatz do zmiennej $ai zapisuje w tablicy, @cże wartość została zauważona, a następnie po osiągnięciu 0 lub 1 zwiększa się, $aaż będzie liczbą, która nie została jeszcze zauważona. Jest to powtarzane kilka razy równe wartości wejściowej minus 2, a na koniec wartość $ajest wyprowadzana.

Mathematica, 134 bajty

f=If[EvenQ@#,#/2,3#+1]&;a@n_:=(b={i=c=0};While[i++<n-1,c=First[Range@Max[#+1]~Complement~#&@b];b=b~Union~NestWhileList[f,c,f@#>c&]];c)

Łatwiejszy do odczytania format:

f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
  b = {i = c = 0};                                   initializations
                                                       b is the growing sequence
                                                       of cycles already completed
  While[i++ < n - 1,                                 computes a(n) recursively
    c = First[Range@Max[# + 1]~Complement~# & @b];   smallest number not in b
    b = b~Union~NestWhileList[f, c, f@# > c &]       apply f to c repeatedly
                                                       until the answer is smaller
                                                       than c, then add this new
                                                       cycle to b
    ]
  ; c)                                                 output final value of c