La suite de Syracuse

Énoncé de la conjecture - Idées de programmation - Calculer les termes de la suite de Syracuse en ligne - Records

Commentaires sur la conjecture de Collatz

Le problème 3x+1, ou conjecture de Syracuse ou de Collatz (du nom du mathématicien qui l'a formulée), est d'une étonnante simplicité, mais il résiste pourtant aux efforts des mathématiciens pour le démontrer (ou l'infirmer) depuis le milieu du XX^e siècle. C'est pour cela que son énoncé reste une conjecture.

Cette conjecture a été formulée par Lothar Collatz en 1937 et s'est répandue vers 1950 grâce notamment à l'université de Syracuse, d'où le nom. Ses noms sont d'ailleurs nombreux : conjecture de Collatz, conjecture de Syracuse ou problème de 3x+1. Un problème qui reste entièrement ouvert encore aujourd'hui.

La suite de Syracuse de Collatz (Lothar Collatz)

On choisit un nombre entier strictement positif :

• Si le nombre est pair, on le divise par 2 et on obtient le terme suivant de la suite.
• Si le nombre est impair, on le multiplie par 3, on ajoute 1 au résultat et on obtient le terme suivant de la suite.

On recommence la procédure avec le nouveau nombre obtenu.

On obtient une suite de nombres qui est appelée :

• le vol du nombre de départ ;
• les nombres de la suite sont appelés les étapes du vol ;
• le plus grand nombre obtenu dans la suite est appelé l'altitude maximale du vol ;
• le nombre d'étapes avant de passer sous le nombre de départ est appelé la durée du vol en altitude ;
• le nombre d'étapes avant d'obtenir 1 est appelé la durée du vol.

Une fois atteint le nombre 1, la suite des valeurs (1, 4, 2, 1, 4, 2…) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.

Nous pouvons définir la suite sous la forme qui suit, pour tout entier naturel n :

$$u_{n+1}=\{\begin{array}{ll}{\displaystyle \frac{u_n}{2}}& \text{si}{u}_n\text{est pair}\\ 3u_n+1& \text{si}{u}_n\text{est impair}\end{array}$$

Conjecture de Syracuse Collatz

Quel que soit le nombre de départ, dans la suite obtenue avec l'algorithme de Syracuse de Collatz, on finit toujours par obtenir 1.

Mais, pour le moment, cela reste une conjecture et aucune preuve (démonstration) n'a été établie à ce jour.

Les avancées

(énoncés équivalents à la conjecture)

La conjecture de Syracuse est équivalente à l’un des énoncés suivants :

(1) la durée de tout vol est finie ;

(2) la durée de tout vol en altitude est finie ;

(3) tout vol a un nombre fini d’étapes paires ;

(4) tout vol a un nombre fini d’étapes paires en altitude ;

(5) tout vol a un nombre fini d’étapes impaires ;

(6) tout vol a un nombre fini d’étapes impaires en altitude.

En 2019, Terence Tao a montré que presque toutes les trajectoires descendent très bas ; par ordinateur, la conjecture a été vérifiée pour tous les entiers jusqu'à 2⁶⁸ (vérification publiée en 2020). La conjecture reste ouverte.

Les termes de la suite de Syracuse pour les nombres de 2 à 11, puis 27, 97 et 99

Pour les nombres de 2 à 11 nous obtenons :

2 - 1

La durée du vol pour 2 est de 1 et son altitude est de 2.

3 - 10 - 5 - 16 - 8 - 4 - 2 - 1

La durée du vol pour 3 est de 7 et son altitude est de 16.

4 - 2 - 1

La durée du vol pour 4 est de 2 et son altitude est de 4.

5 - 16 - 8 - 4 - 2 - 1

La durée du vol pour 5 est de 5 et son altitude est de 16.

6 - 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1

La durée du vol pour 6 est de 8 et son altitude est de 16.

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

La durée du vol pour 7 est de 16 et son altitude est de 52.

8 - 4 - 2 - 1

La durée du vol pour 8 est de 3 et son altitude est de 8.

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

La durée du vol pour 9 est de 19 et son altitude est de 52.

10 - 5 - 16 - 8 - 4 - 2 - 1

La durée du vol pour 10 est de 6 et son altitude est de 16.

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

La durée du vol pour 11 est de 14 et son altitude est de 52.

Pour 27 nous obtenons :

27 - 82 - 41 - 124 - 62 - 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

La durée du vol pour 27 est de 111 et son altitude est de 9232.

Pour 97 nous obtenons :

97 - 292 - 146 - 73 - 220 - 110 - 55 - 166 - 83 - 250 - 125 - 376 - 188 - 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

La durée du vol pour 97 est de 118 et son altitude est de 9232.

C'est la même altitude maximale que pour 27 !

Nous pouvons remarquer que pour 99 nous obtenons une durée de vol beaucoup plus courte que pour 97 :

99 - 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

La durée du vol pour 99 est de 25 et son altitude est de 448.

La suite de Syracuse nous donne des résultats étonnants, qui sont impossibles à prévoir ! Essayez de trouver le plus long vol ou la plus haute altitude. Pour ma part, je trouve 703 ou 871 intéressants.

Calculer le vol, la durée et l'altitude maximale d'un nombre

À vous de jouer… On ouvre un concours : qui trouvera la plus longue durée de vol ?

Vous pouvez par exemple tester avec le calculateur ci-dessous (ou sur calculis.net) les nombres 703 et 871 qui sont, pour une valeur inférieure à 1000, les plus intéressants : l'un détient le record d'altitude et le second le record de durée, pour tous les nombres inférieurs à 1000.

Programmation de l'algorithme de Syracuse

Après avoir rédigé cette page, j’ai eu envie de voir ce que l'on pouvait faire en programmation, pour un simple mortel, c'est-à-dire :

• sans accès à du temps sur un très gros calculateur ;
• et sans avoir de bagage théorique permettant d’apprécier les dernières publications.

Mais c’est l’avantage de la conjecture : nous pouvons nous amuser et réussir quelques calculs sans travailler au CNRS.

Les conditions étaient pour moi très réduites : un ordinateur portable, pas de logiciel qui me permettrait de compiler du C, j'étais donc réduit à monter un serveur web et à lancer une page web avec un programme de calcul rédigé en PHP : c'était le plus rapide et le plus simple à mettre en œuvre pour pouvoir tester des idées d'algorithmes.

Bref ! En reprenant les infos que l’on peut trouver sur la toile (enfin celles que les chercheurs veulent bien nous laisser) et en combinant cela avec les conditions particulières énoncées précédemment, voilà ce que j’ai pu obtenir en quelques jours de programmation et quelques heures de calcul.

Voici par exemple l'algorithme qui calcule la durée du vol et l'altitude maximale d'un nombre, écrit en Python :

def vol(n):
    duree = 0
    altitude = n
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        duree = duree + 1
        altitude = max(altitude, n)
    return duree, altitude

print(vol(27))   # affiche (111, 9232)

Records d'altitude

n° - terme - durée en alt - alt max
1 - 27 - 96 - 9 232
2 - 447 - 65 - 39 364
3 - 639 - 37 - 41 524
4 - 703 - 132 - 250 504
5 - 1819 - 99 - 1 276 936
6 - 4255 - 114 - 6 810 136
7 - 4591 - 106 - 8 153 620
8 - 9663 - 88 - 27 114 424
9 - 20895 - 117 - 50 143 264
10 - 26623 - 106 - 106 358 020
11 - 31911 - 96 - 121 012 864
12 - 60975 - 207 - 593 279 152
13 - 77671 - 171 - 1 570 824 736
14 - 113383 - 179 - 2 482 111 348
15 - 138367 - 96 - 2 798 323 360
16 - 159487 - 117 - 17 202 377 752
17 - 270271 - 267 - 24 648 077 896
18 - 665215 - 228 - 52 483 285 312
19 - 704511 - 119 - 56 991 483 520
20 - 1042431 - 277 - 90 239 155 648
21 - 1212415 - 171 - 139 646 736 808
22 - 1441407 - 243 - 151 629 574 372
23 - 1875711 - 158 - 155 904 349 696
24 - 1988859 - 220 - 156 914 378 224
25 - 2643183 - 298 - 190 459 818 484
26 - 2684647 - 161 - 352 617 812 944
27 - 3041127 - 161 - 622 717 901 620
28 - 3873535 - 202 - 858 555 169 576
29 - 4637979 - 254 - 1 318 802 294 932
30 - 5656191 - 326 - 2 412 493 616 608
31 - 6416623 - 228 - 4 799 996 945 368
32 - 6631675 - 362 - 60 342 610 919 632
33 - 19638399 - 430 - 306 296 925 203 752
34 - 38595583 - 295 - 474 637 698 851 092
35 - 80049391 - 396 - 2 185 143 829 170 100
36 - 120080895 - 331 - 3 277 901 576 118 580
37 - 210964383 - 388 - 6 404 797 161 121 264
38 - 319804831 - 427 - 1 414 236 446 719 942 480

Records de durée en altitude

J'ai découvert que l'on pouvait compiler du C sur mon MacBook ! Eh oui, c'est livré avec le portable ! J'ai donc recompilé le tout en C, en améliorant l’algorithme : cette fois-ci, tout va beaucoup plus vite et j'ai pu obtenir les records de vol en altitude ci-dessous en quelques centaines de secondes ! Après la suite de Syracuse de premier terme 12 235 060 455, le record suivant semble beaucoup moins abordable pour mon algorithme et ma machine : après une heure de calculs, j’obtiens un résultat sûrement faux car l’altitude dépasse les capacités des entiers long long en C. Dommage ! J’ai bien tenté de créer une structure pour gérer les très grands entiers mais cela ralentit considérablement les calculs.

Records de durée en altitude avec le programme en C

27 - 96 - 9232 - 0.000005 s
703 - 132 - 250504 - 0.000107 s
10087 - 171 - 2484916 - 0.000183 s
35655 - 220 - 41163712 - 0.000361 s
270271 - 267 - 24648077896 - 0.001860 s
362343 - 269 - 565335124 - 0.002447 s
381727 - 282 - 565335124 - 0.002578 s
626331 - 287 - 7222283188 - 0.004115 s
1027431 - 298 - 17808240724 - 0.006625 s
1126015 - 365 - 90239155648 - 0.007248 s
8088063 - 401 - 16155154672 - 0.051004 s
13421671 - 468 - 1591706254336 - 0.084490 s
20638335 - 476 - 89243211616 - 0.129836 s
26716671 - 486 - 3696858621088 - 0.167983 s
56924955 - 502 - 7209046267252 - 0.357630 s
63728127 - 613 - 966616035460 - 0.400345 s
217740015 - 644 - 2516021527120 - 1.366941 s
1200991791 - 649 - 35681506677556 - 7.537392 s
1827397567 - 706 - 118736698851769012 - 11.468214 s
2788008987 - 729 - 81887769175732 - 17.496869 s
12235060455 - 892 - 1037298361093936 - 76.827696 s