Voici la conjecture de Collatz (OEIS A006577 ):

• Commencez avec un entier n > 1.
• Répétez les étapes suivantes:
  • Si n est pair, divisez-le par 2.
  • Si n est impair, multipliez-le par 3 et ajoutez 1.

Il est prouvé que pour tous les entiers positifs jusqu’à 5 * 2 ⁶⁰ , soit environ 5764000000000000000 , n finira par devenir 1 .

Votre tâche consiste à déterminer le nombre d’itérations (en divisant par deux ou en triplant plus une) pour atteindre 1 .

Xkcd pertinent :)

Règles:

• Le code le plus court gagne.
• Si un nombre <2 est entré ou un nombre non entier ou non, la sortie n'a pas d'importance.

Cas de test

2  -> 1
16 -> 4
5  -> 5
7  -> 16

GolfScript, 24 23 21 20 18 caractères

~{(}{3*).2%6\?/}/,

Suppose une entrée sur stdin. Test en ligne

C - 50 47 caractères

Pauvre petit C nécessite malheureusement une énorme quantité de code pour les E / S de base, aussi, raccourcir tout cela a rendu l’interface utilisateur légèrement peu intuitive.

b;main(a){return~-a?b++,main(a&1?3*a+1:a/2):b;}

Compilez-le avec par exemple gcc -o 1 collatz.c. L'entrée est unaire avec des chiffres séparés par des espaces et vous trouverez la réponse dans le code de sortie. Un exemple avec le numéro 17:

$> ./1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$> echo $?
12
$>

Perl 34 (+1) caractères

$\++,$_*=$_&1?3+1/$_:.5while$_>1}{

Abuser $\pour le résultat final, comme d'habitude. Exécuter avec l' -poption de ligne de commande, l'entrée est prise à partir de stdin.

Un octet enregistré dû à Elias Van Ootegem . Plus précisément, il est observé que les deux suivants sont équivalents:

$_=$_*3+1
$_*=3+1/$_

Bien que un octet plus, il enregistre deux octets en raccourcissant $_/2juste .5.

Exemple d'utilisation:

$ echo 176 | perl -p collatz.pl
18

PHP 54 octets

<?for(;1<$n=&$argv[1];$c++)$n=$n&1?$n*3+1:$n/2;echo$c;

L'archnémèse de Javascript pour le prix de la cuillère en bois semble être un peu à la hauteur de ce défi. Ce problème ne laisse toutefois pas beaucoup de place à la créativité. L'entrée est considérée comme un argument de ligne de commande.

Exemple d'utilisation:

$ php collatz.php 176
18

Mathematica (35)

If[#>1,#0@If[OddQ@#,3#+1,#/2]+1,0]&

Usage:

If[#>1,#0[If[OddQ@#,3#+1,#/2]]+1,0]&@16
>> 4

Comme d'habitude, je commencerai les réponses par les miennes.

JavaScript, 46 44 caractères (exécuté sur la console)

for(n=prompt(),c=1;n>1;n=n%2?n*3+1:n/2,++c)c

Java, 165, 156, 154,134,131,129,128 , 126 (les langues verbeuses ont besoin d'amour aussi)

class a{public static void main(String[]a){for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y));}}

Tout est fait à l'intérieur du pour

for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y))

C'est paniquer bel homme. Merci à Pater Taylor !!!, et l’idée d’utiliser une boucle for a été volée à ugoren

J'ai remplacé Integer pour Short.

Rebmu : 28

u[++jE1 AeEV?a[d2A][a1M3a]]j

Sur un problème aussi bref et mathématique, GolfScript gagnera probablement quelques pour cent contre Rebmu (si vous n’avez pas à le dire, lisez des fichiers sur Internet ou générez des fichiers JPG). Pourtant, je pense que la plupart des gens conviendraient que la logique de Golfscript est loin d’être aussi facile à suivre, et que la pile exécutable totale qui l’exécute est plus grande.

Bien propre créateur de Rebol Carl Sassenrath m'a dit qu'il a trouvé Rebmu « illisible », il est occupé et n'a pas le temps de vraiment pratiquer la transformation de porc-latin comme par unmushing . Ceci est simplement transformé en:

u [
    ++ j
    e1 a: e ev? a [
        d2 a
    ] [
        a1 m3 a
    ]
]
j

Notez que l’espace était requis pour obtenir un a: au lieu d’ un . Ceci est un "mot de passe!" et l'évaluateur remarque que ce type de symbole déclenche l'affectation.

S'il était écrit en langage non abrégé (Rebol pourtant écrit maladroitement), vous obtiendriez:

until [
    ++ j
    1 == a: either even? a [
        divide a 2
    ] [
        add 1 multiply 3 a
    ]
 ]
 j

Rebol, comme Ruby, évalue les blocs à leur dernière valeur. La boucle UNTIL est une forme de boucle curieuse qui ne prend pas de condition de boucle. Elle arrête simplement de faire une boucle lorsque son bloc est évalué à quelque chose qui n'est pas FALSE ou NONE. Donc, au moment où 1 ==le résultat de l'affectation de A (l'argument à rebmu) au résultat du conditionnel de Collatz (ou bien un IF-ELSE qui correspond à la branche de son choix) ... la boucle se rompt.

J et K sont initialisés à la valeur entière zéro dans Rebmu. Et comme mentionné ci-dessus, le tout est évalué à la dernière valeur. Ainsi, une référence J à la fin du programme signifie que vous obtenez le nombre d'itérations.

Usage:

>> rebmu/args [u[++jE1 AeEV?a[d2A][a1M3a]]j] 16
== 4

Python repl, 48

Je ne suis pas convaincu qu'il n'y ait pas d'expression plus courte que n=3*n+1;n/=1+n%2*5;. J'ai probablement trouvé une douzaine d'expressions différentes de la même longueur ...

i=0
n=input()
while~-n:n=3*n+1;n/=1+n%2*5;i+=1
i

edit: J'ai trouvé une autre solution qui ne se disputera jamais, mais qui est trop amusante pour ne pas être partagée.

s='s'
i=s
n=i*input()
while 1:
 while n==n[::2]+n[::2]:i+=s;n=n[::2]
 if n==s:i.rindex(s);break
 n=3*n+s
 i+=s

APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕

J, 30 caractères

<:#-:`(1+3&*)`]@.(2&|+1&=)^:a:

S'est avéré un peu plus long que souhaité

usage:

   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:2
1
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:16
4
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:5
5
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:7
16
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:27
111

• -:`(1+3&*)`]est un gérond composé de trois verbes, utilisé à trois reprises. -:signifie "divise en deux", (1+3&*)ou (1+3*])encode l'étape de multiplication et la ]terminaison des aides (d'identité).

• 2&|+1&=forme un index pour le gérondif. littéralement, "le reste après division par deux plus s'il est égal à un".

• #verb^:a:itère la fonction jusqu'à ce que le résultat soit stable (ici, forcé explicitement), lors de la collecte des étapes, puis les compte. Volé de @JB . <:décrémente le nombre de pas d'une unité pour s'aligner sur les exigences de la question.

Schéma de jeu, 106 98 caractères, 40 parenthèses

(let((f(lambda(x)(cond((= x 1) 0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))))(f(read)))

91 89 caractères avec définir directement

(define(f x)(cond((= x 1)0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))(f(read))

PowerShell: 77 74 71 70 61

Code de golf:

for($i=(read-host);$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x

Remarques:

À l’origine, j’essayais de prendre l’entrée de l’utilisateur sans la forcer à un nombre entier, mais c’était cassant de manière intéressante. Tous les intrants impairs seraient traités de manière imprécise, mais même les intrants fonctionneraient correctement. Il m'a fallu une minute pour comprendre ce qui se passait.

Lors de la multiplication ou de l'addition, PowerShell considère d'abord les entrées non typées comme des chaînes. Ainsi, '5'*3+1devient "5551" au lieu de 16. Les entrées paires se sont bien comportées car PowerShell ne dispose pas d'une action par défaut pour la division contre les chaînes. Même les entrées paires qui progressaient dans les nombres impairs fonctionnaient bien car, au moment où PowerShell avait atteint un nombre impair dans la boucle, la variable était déjà forcée à un entier par les opérations mathématiques.

Merci à Danko Durbic de m'avoir signalé que je pouvais simplement inverser l'opération de multiplication et ne pas avoir à transtyper read-hostvers int puisque PowerShell base ses opérations sur le premier objet.

Conseil de PowerShell Golfer: Pour certains scénarios, comme celui-ci, switchbat if/else. Ici, la différence était de 2 caractères.

Protip, gracieuseté de Danko Durbic : Pour ce scénario particulier, un tableau peut être utilisé à la place de switch, pour sauvegarder 8 caractères supplémentaires!

Il n'y a pas d'erreur de vérification pour les valeurs non-entières, ou les entiers inférieurs à deux.

Si vous souhaitez vérifier le script, insérez-le ;$ijuste avant la dernière accolade.

Je ne sais pas exactement dans quelle mesure PowerShell gère les nombres qui évoluent vers des valeurs très grandes, mais je m'attends à ce que la précision disparaisse à un moment donné. Malheureusement, je m'attends aussi à ce qu'il n'y ait pas grand chose à faire à ce sujet sans gravement gonfler le script.

Ungolfed code, avec des commentaires:

# Start for loop to run Collatz algorithm.
# Store user input in $i.
# Run until $i reaches 1.
# Increment a counter, $x, with each run.
for($i=(read-host);$i-ne1;$x++)
{
    # New $i is defined based on an array element derived from old $i.
    $i=(
        # Array element 0 is the even numbers operation.
        ($i/2),
        # Array element 1 is the odd numbers operation.
        (3*$i+1)
    # Array element that defines the new $i is selected by $i%2.
    )[$i%2]
}

# Output $x when the loop is done.
$x

# Variable cleanup. Don't include in golfed code.
rv x,i

Cas de test:

Vous trouverez ci-dessous des exemples d’audit activé. J'ai également modifié la sortie pour plus de clarté, en ajoutant des étiquettes à l'entrée et au décompte final et en insérant un espacement pour séparer les valeurs de Collatz.

---
Input: 2

1

Steps: 1

---
Input: 16

8
4
2
1

Steps: 4

---
Input: 5

16
8
4
2
1

Steps: 5

---
Input: 7

22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 16

---
Input: 42

21
64
32
16
8
4
2
1

Steps: 8

---
Input: 14

7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 17

---
Input: 197

592
296
148
74
37
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 26

---
Input: 31

94
47
142
71
214
107
322
161
484
242
121
364
182
91
274
137
412
206
103
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 106

---
Input: 6174

3087
9262
4631
13894
6947
20842
10421
31264
15632
7816
3908
1954
977
2932
1466
733
2200
1100
550
275
826
413
1240
620
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 111

---
Input: 8008135

24024406
12012203
36036610
18018305
54054916
27027458
13513729
40541188
20270594
10135297
30405892
15202946
7601473
22804420
11402210
5701105
17103316
8551658
4275829
12827488
6413744
3206872
1603436
801718
400859
1202578
601289
1803868
901934
450967
1352902
676451
2029354
1014677
3044032
1522016
761008
380504
190252
95126
47563
142690
71345
214036
107018
53509
160528
80264
40132
20066
10033
30100
15050
7525
22576
11288
5644
2822
1411
4234
2117
6352
3176
1588
794
397
1192
596
298
149
448
224
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 93
---

Bits intéressants sur les nombres saisis qui ne proviennent pas des cas de test de la question:

• 14et 197sont des nombres de Keith
• 31est un Mersenne Prime
• 6174est la constante de Kaprekar
• Et enfin, j'aime juste 8008135. Et Numberphile , évidemment.

80386 assembly, 16 octets

Cet exemple utilise la syntaxe AT & T et la convention d'appel fastcall. L'argument est le suivant ecx:

collatz:
        or $-1,%eax              # 3 bytes, eax = -1;
.Loop:  inc %eax                 # 1 byte,  eax += 1;
        lea 1(%ecx,%ecx,2),%edx  # 4 bytes, edx = 3*ecx + 1;
        shr %ecx                 # 2 bytes, CF = ecx & 1;
                                 #          ecx /= 2;
                                 #          ZF = ecx == 0;
        cmovc %edx,%ecx          # 3 bytes, if (CF) ecx = edx;
        jnz .Loop                # 2 bytes, if (!ZF) goto .Loop;
        ret                      # 1 byte,  return (eax);

Voici les 16 octets de code machine résultants:

83 c8 ff 40 8d 54 49 01 d1 e9 0f 42 ca 75 f4 c3

Brachylog , 16 octets

1b|{/₂ℕ|×₃+₁}↰+₁

Essayez-le en ligne!

Explication

         Either:
  1        The input is 1.
  b        In which case we unify the output with 0 by beheading the 1
           (which removes the leading digit of the 1, and an "empty integer"
           is the same as zero).
|        Or:
  {        This inline predicate evaluates a single Collatz step on the input.
           Either:
    /₂       Divide the input by 2.
    ℕ        And ensure that the result is a natural number (which is
             equivalent to asserting that the input was even).
  |        Or:
    ×₃+₁     Multiply the input by 3 and add 1.
  }
  ↰        Recursively call the predicate on this result.
  +₁       And add one to the output of the recursive call.

Une solution alternative au même nombre d'octets:

;.{/₂ℕ|×₃+₁}ⁱ⁾1∧

Essayez-le en ligne!

;.          The output of this is a pair [X,I] where X is the input and
            I will be unified with the output.
{/₂ℕ|×₃+₁}  This is the Collatz step predicate we've also used above.
ⁱ⁾          We iterate this predicate I times on X. Since we haven't actually
            specified I, it is still a free variable that Brachylog can backtrack
            over and it will keep adding on iterations until the next
            constraint can be satisfied.
1           Require the result of the iteration to be 1. Once this is
            satisfied, the output variable will have been unified with
            the minimum number of iterations to get here.
∧           This AND is just used to prevent the 1 from being implicitly
            unified with the output variable as well.

GolfScript (23 caractères)

~{.1&{.3*)}*.2/.(}do;],

Test en ligne

F # - 65 caractères

let rec c n=function 1->n|i->c(n+1)(if i%2=0 then i/2 else i*3+1)

Python 68 58 54 52 caractères

f=lambda n:1+(n-2and f((n/2,3*n+1)[n%2]));f(input())

Merci à Bakuriu et Boothby pour les conseils :)

Retina , 43 octets

11
2
(2+)1
$1$1$0$0$0$0
2.*
$0x
)`2
1
1?x
1

Prend l’entrée et imprime la sortie unaire.

Chaque ligne doit aller dans son propre fichier. 1 octet par fichier supplémentaire ajouté au nombre d'octets.

Vous pouvez exécuter le code en tant que fichier unique avec l' -sindicateur. Par exemple:

> echo -n 1111111|retina -s collatz
1111111111111111

L'algorithme est une boucle consistant à faire une étape de Collatz avec le nombre unaire et à ajouter un nouveau marqueur de pas xà la fin de la chaîne si le nombre n'est pas 1.

Lorsque la boucle se termine par 1, nous convertissons les marqueurs en un nombre unaire (en supprimant le premier 1) qui correspond à la sortie souhaitée.

Gelée , non en compétition

12 octets Cette réponse est sans concurrence, car le défi était antérieur à la création de Jelly.

×3‘$HḂ?ß0’?‘

Essayez-le en ligne!

Comment ça fonctionne

×3‘$HḂ?ß0’?‘  Main link. Argument: n (integer)

     Ḃ?       Yield the last bit of n is 1:
   $            Evaluate the three links to the left as a monadic chain:
×3                Multiply n by 3.
  ‘               Increment the product by 1.
    H           Else, halve n.
         ’?   If n-1 is non-zero:
       ß        Recursively call the main link.
        0     Else, yield 0.
           ‘  Increment the result by 1.

dc, 27 caractères

Appliquer la magie noire de boothby :

?[d3*1+d2%5*1+/d1<x]dsxxkzp

Je ne suis pas vraiment sûr de comprendre comment - ou cela - cela fonctionne.

$ dc collatz.dc <<< 7
16

dc, 36 caractères

Ma propre création; Une approche un peu plus traditionnelle, même si j'ai dû lutter un peu avec le langage pour pallier le manque d'éléments elsedans les ifdéclarations:

?[2/2Q]se[dd2%[0=e3*1+]xd1<x]dsxxkzp

En interne, il produit tous les numéros de la séquence et les stocke dans la pile, puis 1affiche la dernière et affiche la hauteur de la pile.

brainfuck , 59 56 octets

,-[<->[[>]+<[-<]>>]>[-<<[++>+<]>->]<<[+>+++<]<<+>>>]<<<.

Essayez-le en ligne! (Légèrement modifié pour la facilité d'utilisation)

Entrée et sortie en tant que codes de caractères. Ceci est plus utile avec des cellules de taille arbitraire, mais peut toujours fonctionner avec de petites valeurs dans des tailles de cellules limitées.

Comment ça fonctionne

Tape Format:
Counter 0 Copy Number Binary...
^End           ^Start

,-[ Get input, decrement by 1 and start loop
  <->                  Initialises the copy of the value at -1
  [[>]+<[-<]>>]        Converts the input to binary while preserving a negative copy
  <+>>[-<<[++>+<]>->] If the last digit of the binary is 1 (n-1 is odd), divide by 2 and decrement
  <<[+>+++<]            If the last digit of the binary is 0 (n-1 is even), multiply by 3
  <<+>>>               Increment counter and end on n-1
]<<<.                 End loop and print counter

Hexagonie , 48 44 octets

?(]$_)"){{?{*')}/&!/={:<$["/>&_(.<@2'%<>./>=

Essayez-le en ligne!

Étendu:

     ? ( ] $ _
    ) " ) { { ?
   { * ' ) } / &
  ! / = . { < $ [
 " / > & _ ( . < @
  2 ' % < > : / >
   = . . . . . .
    . . . . . .
     . . . . .

Notez que cela échoue 1pour des raisons euhh . Honnêtement, je ne sais plus trop comment cela fonctionne. Tout ce que je sais, c'est que le code des nombres impairs est inversé pour les nombres pairs? En quelque sorte?

La nouvelle version est beaucoup plus nette que la précédente, mais présente un peu plus de directions et se termine par une erreur de division par zéro. Le seul cas où cela ne se produit pas, c'est quand il gère 1correctement.

C, 70 69 caractères

Assez simple, pas de trucs.
Lit les entrées de stdin.

a;
main(b){
    for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
    printf("%d",a);
}

Q, 46

{i::0;{x>1}{i+:1;$[x mod 2;1+3*x;(_)x%2]}\x;i}

Ruby 1.9, 49 caractères

La réponse Python de Rubyfied Valentin CLEMENT , en utilisant la syntaxe stabby lambda. Sqeezed en une seule déclaration pour plus de lisibilité.

(f=->n{n>1&&1+f[[n/2,3*n+1][n%2]]||0})[gets.to_i]

Certains frais généraux parce que Ruby, contrairement à Python, n'est pas content de mélanger des nombres avec des booléens.

C ++ ( 51 48)

C'est une fonction récursive qui fait cela; la lecture d'entrée vient séparément.

int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}

Je suis sûr que je peux faire un truc "et / ou" avec le == 0truc, mais je ne sais pas comment.

~ - ~! (Pas de commentaire) - 71 53

Cette langue n’est évidemment pas la meilleure pour jouer au golf car elle manque de nombreuses fonctionnalités natives, mais c’est la beauté de celle-ci.

'=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:

Tout d’abord, réglez '''votre saisie. La fonction ''peut alors être appelée avec %comme entrée et renverra la réponse, comme ceci:

'''=~~~~~:''&%:

Cela va revenir ~~~~~. Cela fonctionne réellement pour n==1(il boucle pour toujours n==0).

Comme toujours avec cette langue, non testée.

JavaScript (ES6) - 29 caractères

f=x=>x>1?f(x%2?x*3+1:x/2)+1:0

Crée une fonction fqui accepte un seul argument et renvoie le nombre d'itérations.

JavaScript - 31 caractères

for(c=0;n>1;n=n%2?n*3+1:n/2)++c

Suppose que l’entrée est dans la variable net crée une variable ccontenant le nombre d’itérations (et sera également transmise cà la console en tant que dernière commande).

Perl 6, 40 octets

Méthode de la fonction récursive, selon Valentin CLEMENT et daniero : 40 caractères

sub f(\n){n>1&&1+f n%2??3*n+1!!n/2}(get)

Méthode de liste paresseuse: 32 caractères

+(get,{$_%2??$_*3+1!!$_/2}...^1)

> <>, 27 26 23 octets

\ln;
\::2%:@5*1+2,*+:2=?

Comme l’autre> <> répond, cela construit la séquence sur la pile. Une fois que la séquence atteint 2, la taille de la pile est le nombre de pas effectués.

Grâce à @Hohmannfan, économisez 3 octets grâce à une méthode très intelligente de calcul direct de la valeur suivante. La formule utilisée pour calculer la valeur suivante de la séquence est la suivante:

La fraction mappe les nombres pairs sur 0,5 et les nombres impairs sur 3. Multiplier par net ajouter n%2complète le calcul - nul besoin de choisir la valeur suivante!

Edit 2: Voici la version pré- @ Hohmannfan:

\ln;
\:::3*1+@2,@2%?$~:2=?

L'astuce ici est que les deux 3n+1et n/2sont calculés à chaque étape de la séquence, et l'une à être retirés de la séquence est choisie par la suite. Cela signifie que le code n'a pas besoin de créer de branche jusqu'à ce que 1 soit atteint et que le calcul de la séquence peut se faire sur une ligne de code.

Édition: rejetez un autre caractère après avoir réalisé que le seul entier positif pouvant mener à 1 est 2. Comme la sortie du programme n'a pas d'importance pour l'entrée <2, la génération de séquence peut se terminer lorsque 2 est atteint, laissant ainsi la taille de la pile. étant le nombre exact d'étapes requises.

Version précédente:

\~ln;
\:::3*1+@2,@2%?$~:1=?