Aujourd'hui, nous allons regarder une séquence a , liée à la fonction Collatz f :

Nous appelons une séquence de la forme z, f (z), f (f (z)),… une séquence de Collatz .

Le premier nombre de notre séquence, a (1) , est 0 . Sous l'application répétée de f , il tombe dans un cycle 0 → 0 →…

Le plus petit nombre que nous n'avons pas encore vu est 1, ce qui fait un (2) = 1 . Sous l'application répétée de f , il tombe dans un cycle 1 → 4 → 2 → 1 →…

Maintenant, nous avons vu le nombre 2 dans le cycle ci-dessus, donc le plus petit nombre suivant est a (3) = 3 , tombant dans le cycle 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 →…

Dans tous les cycles ci-dessus, nous avons déjà vu 4 et 5 , donc le nombre suivant est a (4) = 6 .

Vous devriez maintenant avoir l'idée. a (n) est le plus petit nombre qui ne faisait partie d'aucune séquence de Collatz pour tous a (1),…, a (n - 1) .

Écrivez un programme ou une fonction qui, étant donné un entier positif n , renvoie a (n) . Le code le plus court en octets gagne.

Testcases:

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

(Il s'agit de la séquence OEIS A061641 .)

Gelée , 20 19 octets

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

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça marche

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

Après n itérations, la valeur de a (n + 1) sera au début du tableau. Puisque nous concaténons le nouveau tableau avec une copie inversée de l'ancien, cela signifie qu'un (n) sera à la fin.

Haskell, 93 92 octets

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

Exemple d'utilisation: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10-> 19.

c xest le cycle Collatz pour xavec un peu de triche pour x == 1. Les principales fonctions boucle dans tous les entiers et maintient ceux qui ne sont pas c xpour xen [0..y-1]. À peu près une mise en œuvre directe de la définition. Comme l'opérateur d'index Haskell !!est basé sur 0, je commence par -1ajouter un nombre (sinon inutile) pour obtenir l'index fixe.

MATL , 46 40 octets

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

Essayez-le en ligne!

Explication

Le code a une forboucle externe qui génère des nséquences Collatz, une à chaque itération. Chaque séquence est générée par une do...whileboucle interne qui calcule de nouvelles valeurs et les stocke dans un vecteur de séquence jusqu'à ce que a 1ou 0soit obtenu. Une fois la séquence terminée, le vecteur est inversé et concaténé en un vecteur global qui contient les valeurs de toutes les séquences précédentes. Ce vecteur peut contenir des valeurs répétées. L'inversion du vecteur de séquence garantit qu'à la fin de la boucle externe le résultat souhaité (la valeur de départ de la dernière séquence) sera à la fin du vecteur global.

Pseudo-code :

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

Code commenté :

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 octets

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

Essayez-le en ligne!

Python 2, 97 96 octets

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

Profite du fait que tous les multiples de 3 sont purs. Testez-le sur Ideone .

Comment ça marche

Sur la première ligne, r,=s={-1}définit s = {-1} (set) et r = -1 .

Ensuite, nous lisons un entier de STDIN, répétons une certaine chaîne plusieurs fois, puis l'exécutons. Ceci est équivalent au code Python suivant.

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]

Dans chaque itération, nous commençons par trouver le plus petit membre de {r + 1, r + 2, r + 3} qui n'appartient pas à s . Dans la première itération, cela initialise r à 0 .

Dans toutes les exécutions suivantes, s peut (et contiendra) une partie de r + 1 , r + 2 et r + 3 , mais jamais tous, car tous les multiples de 3 sont purs. Pour vérifier cette affirmation, notez qu'aucun multiple m de 3 n'est de la forme 3k + 1 . Cela laisse 2m comme seule pré-image possible, qui est également un multiple de 3 . Ainsi, m ne peut apparaître dans la séquence de Collatz d'aucun nombre inférieur à m , et est donc pur.

Après avoir identifié r et initialisé n , nous appliquons la fonction Collatz avec n=(n/2,3*n+1)[n%2], en ajoutant chaque valeur intermédiaire de n à l'ensemble s avec s|={n}. Une fois que nous rencontrons un nombre n qui est déjà dans s , {n}-scela donnera un ensemble vide et l'itération s'arrêtera.

La dernière valeur de r est l'élément souhaité de la séquence.

Pyth , 32 octets

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

Suite de tests.

Java, 148 octets

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! (Attention: complexité exponentielle due à une optimisation nulle.)

La convertir d'une do...whileboucle en forboucle serait plus golfique, mais j'ai du mal à le faire.

Les conseils de golf sont les bienvenus comme d'habitude.

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;

Basé sur la réponse Perl 5 . Un peu plus longtemps car la syntaxe Perl6 est moins indulgente que la syntaxe Perl5, mais je vais me contenter de cela pour l'instant.

PHP, 233 124 octets

<?$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 pour la fonction:

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 octets

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

Il s'agit d'une solution assez simple. Il applique à plusieurs reprises la fonction Collatz à la variable $aet stocke dans le tableau @cque la valeur a été vue, puis après avoir atteint 0 ou 1, il incrémente $ajusqu'à ce que ce soit un nombre qui n'a pas encore été vu. Ceci est répété un nombre de fois égal à l'entrée moins 2, et enfin la valeur de $aest sortie.

Mathematica, 134 octets

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)

Format plus facile à lire:

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