Hoje veremos uma sequência a , relacionada à função Collatz f :

Chamamos uma sequência da forma z, f (z), f (f (z)),… uma sequência Collatz .

O primeiro número da nossa sequência, a (1) , é 0 . Sob aplicação repetida de f , ele entra em um ciclo 0 → 0 →…

O menor número que ainda não vimos é 1, produzindo um (2) = 1 . Sob aplicação repetida de f , ele entra em um ciclo 1 → 4 → 2 → 1 →…

Agora vimos o número 2 no ciclo acima, então o próximo número menor é um (3) = 3 , caindo no ciclo 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 →…

Em todos os ciclos acima, vimos 4 e 5 , então o próximo número é (4) = 6 .

Até agora você deve ter uma ideia. a (n) é o menor número que não fazia parte de nenhuma sequência de Collatz para todos os a (1),…, a (n - 1) .

Escreva um programa ou função que, dado um número inteiro positivo n , retorne a (n) . O menor código em bytes vence.

Casos de teste:

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

(Essa é a sequência OEIS A061641 .)

Geléia , 20 19 bytes

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

Experimente online! ou verifique todos os casos de teste .

Como 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.

Após n iterações, o valor de a (n + 1) estará no início da matriz. Como concatenamos a nova matriz com uma cópia invertida da antiga, isso significa que a (n) estará no 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]]!!)

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

c xé o ciclo de Collatz xcom um pouco de trapaça x == 1. As principais funções percorre todos os inteiros e mantém aqueles que não estão em c xpara xem [0..y-1]. Praticamente uma implementação direta da definição. Como o operador de índice Haskell !!é baseado em 0, começo por -1um número (de outra forma inútil) para obter o índice fixo.

MATL , 46 40 bytes

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

Experimente online!

Explicação

O código possui um forloop externo que gera nsequências Collatz, uma em cada iteração. Cada sequência é gerada por um do...whileloop interno que calcula novos valores e os armazena em um vetor de sequência até que a 1ou 0seja obtido. Quando terminamos a sequência, o vetor é revertido e concatenado para um vetor global que contém os valores de todas as seqüências anteriores. Esse vetor pode conter valores repetidos. A reversão do vetor de sequência garante que, no final do loop externo, o resultado desejado (o valor inicial da última sequência) esteja no final do vetor global.

Pseudo-có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.

Experimente online!

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

Aproveita o fato de que todos os múltiplos de 3 são puros. Teste em Ideone .

Como funciona

Na primeira linha, r,=s={-1}define s = {-1} (conjunto) er = -1 .

Em seguida, lemos um número inteiro de STDIN, repetimos uma certa string várias vezes e depois executamos. Isso é equivalente ao seguinte código 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]

Em cada iteração, começamos encontrando o menor membro de {r + 1, r + 2, r + 3} que não pertence a s . Na primeira iteração, isso inicializa r como 0 .

Em todas as execuções subsequentes, s pode (e irá) conter parte de r + 1 , r + 2 e r + 3 , mas nunca todas, uma vez que todos os múltiplos de 3 são puros. Para verificar esta afirmação, observe que nenhum m múltiplo de 3 tem a forma 3k + 1 . Isso deixa 2m como a única pré-imagem possível, que também é um múltiplo de 3 . Assim, m não pode aparecer na sequência Collatz de qualquer número que seja menor que m e, portanto, é puro.

Após identificar r e inicializar n , aplicamos a função Collatz com n=(n/2,3*n+1)[n%2], adicionando cada valor intermediário de n ao conjunto s com s|={n}. Quando encontrarmos um número n que já está em s , {n}-sproduzirá um conjunto vazio e a iteração será interrompida.

O último valor de r é o elemento desejado da sequência.

Pitão , 32 bytes

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

Suíte de teste.

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! (Aviso: complexidade exponencial devido à otimização zero.)

Convertê-lo de um do...whileloop para um forloop seria mais golfista, mas estou tendo problemas para fazê-lo.

Conselhos sobre golfe são bem-vindos, como de costume.

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;

Baseado na resposta do Perl 5 . Um pouco mais, já que a sintaxe do Perl6 é menos tolerante que a sintaxe do Perl5, mas vou resolver isso por enquanto.

PHP, 233 124 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 função:

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 é uma solução bastante direta. Aplica repetidamente a função Collatz à variável $ae armazena na matriz @cque o valor foi visto; depois de atingir 0 ou 1, aumenta $aaté que seja um número que ainda não foi visto. Isso é repetido um número de vezes igual à entrada menos 2 e, finalmente, o valor de $aé emitido.

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 mais fácil de ler:

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