Hoy veremos una secuencia a , relacionada con la función Collatz f :

Llamamos a una secuencia de la forma z, f (z), f (f (z)), ... una secuencia de Collatz .

El primer número en nuestra secuencia, a (1) , es 0 . Bajo la aplicación repetida de f , cae en un ciclo 0 → 0 →…

El número más pequeño que aún no hemos visto es 1, haciendo un (2) = 1 . Bajo la aplicación repetida de f , cae en un ciclo 1 → 4 → 2 → 1 →…

Ahora hemos visto el número 2 en el ciclo anterior, por lo que el siguiente número más pequeño es un (3) = 3 , que cae en el ciclo 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 →…

En todos los ciclos anteriores ya hemos visto 4 y 5 , por lo que el siguiente número es a (4) = 6 .

A estas alturas ya deberías tener la idea. a (n) es el número más pequeño que no fue parte de ninguna secuencia de Collatz para todos a (1), ..., a (n - 1) .

Escriba un programa o función que, dado un entero positivo n , devuelva a (n) . El código más corto en bytes gana.

Casos de prueba:

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

(Esta es la secuencia OEIS A061641 .)

Jalea , 20 19 bytes

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

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

Ç¡Ṫ              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.

Después de n iteraciones, el valor de a (n + 1) estará al comienzo de la matriz. Como concatenamos la nueva matriz con una copia invertida de la anterior, esto significa que un (n) estará al final.

Haskell, 93 92 bytes

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]]!!)

Ejemplo de uso: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10-> 19.

c xes el ciclo de Collatz para xcon un poco de trampa x == 1. Las principales funciones de bucle a través de todos los números enteros y mantiene los que no están en c xpara xen [0..y-1]. Prácticamente una implementación directa de la definición. Como el operador de índice de Haskell !!está basado en 0, comienzo -1a anteponer un número (de lo contrario inútil) para arreglar el índice.

MATL , 46 40 bytes

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

Pruébalo en línea!

Explicación

El código tiene un forbucle externo que genera nsecuencias de Collatz, una en cada iteración. Cada secuencia es generada por un do...whilebucle interno que calcula nuevos valores y los almacena en un vector de secuencia hasta que se obtiene a 1o 0. Cuando terminamos con la secuencia, el vector se invierte y concatena a un vector global que contiene los valores de todas las secuencias anteriores. Este vector puede contener valores repetidos. La inversión del vector de secuencia asegura que al final del bucle externo el resultado deseado (el valor inicial de la última secuencia) estará al final del vector global.

Pseudocódigo :

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

Código comentado :

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 bytes

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

Pruébalo en línea!

Python 2, 97 96 bytes

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

Aprovecha el hecho de que todos los múltiplos de 3 son puros. Pruébalo en Ideone .

Cómo funciona

En la primera línea, r,=s={-1}establece s = {-1} (conjunto) yr = -1 .

A continuación, leemos un número entero de STDIN, repetimos cierta cadena muchas veces y luego lo ejecutamos. Esto es equivalente al siguiente código de 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]

En cada iteración, comenzamos por encontrar el miembro más pequeño de {r + 1, r + 2, r + 3} que no pertenece a s . En la primera iteración, esto inicializa r como 0 .

En todas las ejecuciones posteriores, s puede (y tendrá) algunos de r + 1 , r + 2 y r + 3 , pero nunca todos, ya que todos los múltiplos de 3 son puros. Para verificar esta afirmación, observe que ningún múltiplo m de 3 tiene la forma 3k + 1 . Eso deja a 2m como la única imagen previa posible, que también es un múltiplo de 3 . Por lo tanto, m no puede aparecer en la secuencia de Collatz de cualquier número que sea menor que m , y por lo tanto es puro.

Después de identificar r e inicializar n , aplicamos la función Collatz con n=(n/2,3*n+1)[n%2], agregando cada valor intermedio de n al conjunto s con s|={n}. Una vez que encontramos un número n que ya está en s , {n}-sdará un conjunto vacío, y la iteración se detiene.

El último valor de r es el elemento deseado de la secuencia.

Pyth , 32 bytes

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

Banco de pruebas.

Java, 148 bytes

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 it! (Advertencia: complejidad exponencial debido a la optimización cero).

Convertirlo de un do...whilebucle a otro forsería más divertido, pero tengo problemas para hacerlo.

Los consejos de golf son bienvenidos como siempre.

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;

Basado en la respuesta de Perl 5 . Un poco más, ya que la sintaxis Perl6 es menos tolerante que la sintaxis Perl5, pero me conformaré con esto por ahora.

PHP, 233124 bytes

<?$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 para la función:

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 bytes

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

Esta es una solución bastante sencilla. Aplica repetidamente la función Collatz a la variable $ay almacena en la matriz @cque se ha visto el valor, luego, después de alcanzar 0 o 1, se incrementa $ahasta que es un número que aún no se ha visto. Esto se repite varias veces igual a la entrada menos 2, y finalmente $ase emite el valor de .

Mathematica, 134 bytes

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)

Formato más fácil de leer:

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