La conjecture de Collatz postule que si vous prenez un entier positif, répétez l'algorithme suivant suffisamment de fois:

if number is odd, then multiply by three and add one
if number is even, then divide by two

vous finirez par finir à 1. Cela semble toujours fonctionner, mais il n'a jamais été prouvé que cela fonctionne toujours.

Vous avez déjà joué au golf en calculant le temps qu'il faut pour arriver à 1 , alors j'ai pensé changer un peu les choses.

En partant d'un entier positif donné, calculez le temps qu'il faut pour arriver à 1 (son «temps d'arrêt»). Trouvez ensuite l'heure d'arrêt de ce numéro.

Répétez jusqu'à ce que vous atteigniez 1, ou jusqu'à ce que vous atteigniez la limite entièrement arbitraire de 100 itérations. Dans le premier cas, indiquez le nombre d'itérations nécessaires. Dans ce dernier cas, imprimez "Fail" ou une autre sortie cohérente de votre choix, tant qu'il ne s'agit pas d'un entier 1≤n≤100. Vous ne pouvez pas générer de chaîne vide pour cette option. La sortie d'un entier en dehors de la plage [1, 100] est cependant autorisée.

Exemples:

Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6

Comme je l'ai calculé 10^100et en 12345678901234567890utilisant une langue qui ne prend en charge que les réels pour cette taille, si votre langue est plus précise, vous pouvez obtenir des résultats différents pour ceux-ci.

Notation

Comme il s'agit de code-golf , la réponse avec le plus petit nombre d'octets l'emporte.

Gelée , 24 octets

×3‘$HḂ?’пL’
Ç1¹?ȷ2Сi1’

Essayez-le en ligne!

Python 2 , 70 octets

f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)

Renvoie 199 pour cent ou plusieurs itérations.

Essayez-le en ligne!

Attaché , 40 octets

`-&3@`#@PeriodicSteps[CollatzSize@Max&1]

Essayez-le en ligne!

Ceci est un nouveau langage que j'ai créé. Je voulais me familiariser avec la création d'un langage d'infixe approprié, et voici le résultat: un knock-off mathématique. Hourra?

Explication

Il s'agit d'une composition de quelques fonctions. Ces fonctions sont:

• PeriodicSteps[CollatzSize@Max&1]Cela donne une fonction qui applique son argument jusqu'à ce que les résultats contiennent un élément en double. Cette fonction ,, CollatzSize@Max&1s'applique CollatzSizeà la plus grande des entrées et 1, pour éviter l'entrée non valide 0à CollatSize.
• `#est un opérateur entre guillemets; appliqué monadiquement dans ce sens, il obtient la taille de son argument
• `-&3est une fonction liée, qui lie l'argument 3à la fonction `-, qui se lit comme «moins 3». En effet, l'application PeriodicSteps donne des 0s, qui doivent être pris en compte. (Il gère également parfaitement les nombres hors limites comme ceux 5qui correspondent à -1.)

J , ₄₉ 45 octets

-4 octets grâce au code Collatz Sequence plus court extrait du commentaire de @ randomra ici .

(2-~[:#(>&1*-:+2&|*+:+>:@-:)^:a:)^:(<101)i.1:

Sorties 101pour des résultats invalides.

Essayez-le en ligne!

Explication

Sans surprise, cette explication est rapidement devenue obsolète. Je vais le laisser en termes de l'ancienne réponse de 49 octets que j'avais, que j'inclus ci-dessous. Si vous voulez une mise à jour, faites le moi savoir. La façon dont il trouve la longueur de la séquence récursive reste la même, je viens d'utiliser une méthode de séquence Collatz plus courte.

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)^:(<101)i.1:

Trouver la longueur de la séquence Collatz

Cette section du code est la suivante

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)

Voici l'explication:

(1 -~ [: # %&2`(1+3&*)@.(2&|) ^: (1&<) ^: a:)  Given an input n
                                       ^: a:   Apply until convergence, collecting
                                                each result in an array.
                              ^: (1&<)         If n > 1 do the following, else
                                                return n.
                        (2&|)                  Take n mod 2.
           %&2                                 If n mod 2 == 0, divide by 2.
               (1+3&*)                         If n mod 2 == 1, multiply by 3 
                                                and add 1.
         #                                     Get the length of the resulting
                                                array.
 1 -~                                          Subtract 1.

Malheureusement, le verbe apply ( ^:) lorsqu'il est invité à stocker les résultats stocke également la valeur initiale, ce qui signifie que nous sommes (comme toujours) décalés d'un. Par conséquent, pourquoi nous soustrayons 1.

Trouver la longueur de la séquence récursive

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:) ^: (< 101) i. 1:  Given an input n.
                                      ^: (< 101)        Apply 100 times,
                                                         collecting results
                                                         in an array.
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)                   Collatz sequence length.
                                                 i. 1:  Index of first 1 (returns
                                                         101, the length of the
                                                         array if 1 not found).

C (gcc) , 75 octets

i,j;f(n){for(j=0;(i=n)&&j++<100;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j-1;}

Renvoie -1pour les n>=100itérations.

Essayez-le en ligne!

C (gcc) , 73 octets

i,j;f(n){for(j=-1;(i=n)&&j++<99;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j;}

Renvoie 0pour les n>=100itérations.

Essayez-le en ligne!

JavaScript (ES6), 57 octets

Retourne en truecas d'échec. Retourne 0pour 1.

f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

Cas de test

f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

console.log(f(2))    // 1
console.log(f(5))    // fail
console.log(f(10))   // 8
console.log(f(100))  // 13
console.log(f(1))    // 0

APL (Dyalog Unicode) , 39 60 53 52 49 octets

-3 octets grâce à @ngn

0∘{99<⍺:⋄1=⍵:0⋄1+(⍺+1)∇{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}⍵}

Essayez-le en ligne!

Utilise le code @ngn pour Collatz, mais utilisait précédemment le code @ Uriel.

Voici l'ancienne version qui ne répondait pas aux spécifications:

{1=⍵:0⋄1+∇{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}⍵}

Perl 6 , 56 octets

{($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}

Essayez-le en ligne!

Renvoie 101une séquence sans fin.

Husk , 21 octets

←€1↑101¡ȯ←€1¡?½o→*3¦2

Essayez-le en ligne! Retourne -1en cas d'échec, 0en entrée 1.

Explication

←€1↑101¡ȯ←€1¡?½o→*3¦2  Implicit input (a number).
             ?½o→*3¦2  Collatz function:
             ?     ¦2   if divisible by 2,
              ½         then halve,
               o→*3     else multiply by 3 and increment.
        ȯ←€1¡?½o→*3¦2  Count Collatz steps:
            ¡           iterate Collatz function and collect results in infinite list,
          €1            get 1-based index of 1,
        ȯ←              decrement.
       ¡               Iterate this function on input,
   ↑101                take first 101 values (initial value and 100 iterations),
←€1                    get index of 1 and decrement.

C (gcc) , 70 73 octets

g(x){x=x-1?g(x%2?3*x+1:x/2)+1:0;}f(x,m){for(m=0;(x=g(x))&&100>m++;);x=m;}

Essayez-le en ligne!

Renvoie 101lorsque le nombre d'itérations dépasse 100.

Nettoyer , 146 ... 86 octets

-11 octets grâce à Ørjan Johansen

import StdEnv
?f l n=hd[u\\1<-iterate f n&u<-l]

?(?(\b|isOdd b=3*b+1=b/2)[0..])[0..99]

Comme une fonction partielle littérale.

Essayez-le en ligne!

Abandonne avec hd of []si le nombre d'itérations dépasse 100.
Quitte avec Heap Fullpour les entrées supérieures à ~ 2^23sauf si vous spécifiez une taille de segment de mémoire plus grande.

Python 2 , 99 98 97 octets

• Enregistré un octet en utilisant c and t or fau lieu de t if c else f.
• Enregistrement d'un octet en produisant à la -1place fou 'f'pour des entrées sans interruption.

exec"f,F="+"lambda n,i=0:n<2and i or %s"*2%("f([n/2,3*n+1][n%2],-~i),","i>99and-1or F(f(n),-~i)")

Essayez-le en ligne!

BiwaScheme , 151 caractères

(define(f n i s)(if(= s 0) 'F(if(= n 0)i(f(letrec((c(lambda(m k)(if(= m 1)k(c(if(=(mod m 2)0)(/ m 2)(+(* m 3)1))(+ k 1))))))(c n 0))(+ i 1)(- s 1)))))

Vous pouvez l'essayer ici .

R , 119 107 octets

Utilise partiellement le code collatz de Jarko Dubbeldam d' ici . Renvoie 0pour> 100 itérations (échec).

pryr::f(x,{N=n=0
while(x-1){while(x-1){x=`if`(x%%2,3*x+1,x/2);n=n+1}
x=n
n=0
N=N+1
if(N==100)return(0)}
N})

Essayez-le en ligne!

APL NARS, 115 octets, 63 caractères

{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}

Probablement en utilisant des boucles, ce serait plus clair ... Il y a 4 fonctions, 2 imbriquées et ricorsives, et la première uniquement pour définir et initialiser à = 0, la variable d, vue de la 2ème fonction comme un compteur de variable globale.

q←{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}

Cette 3ème fonction, serait la fonction qui retourne combien d'appels il y a pour résoudre la conjecture Collatz pour son arg

{⍵=1:d⋄99<d+←1:¯1⋄∇q⍵}

C'est la 2ième fonction, si a son arg = 1, arrête sa récursivité et retourne d le nombre de fois où elle est appelée elle-même-1; sinon, si elle est appelée plus de 99 fois, arrêtez sa récursivité et retournez -1 (échec). Sinon, calculez la conjecture Collatz pour son arg et appelez-la pour la valeur de la longueur de la séquence Collatz. Pour moi, même si tout cela semble exécuté, cela pourrait être un gros problème si l'on définit une variable globale et une variable dans une fonction du même nom, lorsque le programmeur la considère comme une simple variable locale.

  f←{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}     
  f 2
1
  f 3
5
  f 5
¯1
  f 10
8
  f 100
13
  f 12313
7
  f 1
0

(Emacs, Common, ...) Lisp, 105 octets

Renvoie t pour les itérations> 100

(defun f(n k c)(or(> c 100)(if(= n 1)(if(= k 0)c(f k 0(1+ c)))(f(if(oddp
n)(+ n n n 1)(/ n 2))(1+ k)c))))

Étendu:

(defun f (n k c)
  (or (> c 100)
      (if (= n 1)
          (if (= k 0) c
            (f k 0 (1+ c)))
        (f (if (oddp n) (+ n n n 1) (/ n 2))
           (1+ k) c))))
(f (read) 0 0)