La conjecture ou suite de Syracuse
En mathématiques, on appelle suite de Syracuse une suite d'entiers naturels définie de la manière suivante :
- On part d'un nombre entier plus grand que zéro ;
- s'il est pair, on le divise par 2 ;
- s'il est impair, on le multiplie par 3 et on ajoute 1.
- En répétant l'opération, on obtient une suite d'entiers positifs dont chacun ne dépend que de son prédécesseur.
- Par exemple, à partir de 10, on construit la suite des nombres : 5, 16, 8, 4, 2, 1, 4, 2...
C'est ce qu'on appelle la suite de Syracuse du nombre 10.
- Après que le nombre 1 a été atteint, 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.
🔢 Définition mathématique
La suite \((u_n)\) est définie pour tout entier npar :\(u_0=N \in \mathbb{N}^*\) et
$$\forall n \in \mathbb{N}~,~u_{n+1}=\left\lbrace\begin{array}{ll} \dfrac{u_n}{2} & \text{si}~u_n~ \text{pair} \\3u_n+1 & \text{si}~u_n~ \text{impair}\end{array}\right. $$
Exemple : pour \(N = 10\), la suite devient : 5, 16, 8, 4, 2, 1, 4, 2, 1...
🧠 Une conjecture toujours irrésolue
A priori, il serait possible que la suite de Syracuse de certaines valeurs de départ n'atteigne jamais la valeur 1, soit qu'elle aboutisse à un cycle différent du cycle trivial, soit qu'elle diverge vers l'infini. Or, on n'a jamais trouvé d'exemple de suite obtenue suivant les règles données qui n'aboutisse pas à 1 et, par suite, au cycle trivial.
La conjecture de Syracuse, encore appelée conjecture de Collatz, conjecture d'Ulam, conjecture tchèque ou problème 3x+1 est l'hypothèse mathématique selon laquelle la suite de Syracuse de n'importe quel entier strictement positif atteint 1.
Ce qui est magique avec cette conjecture est sa simplicité apparente, et pourtant elle résiste depuis des siècles aux plus grands mathématiciens du monde !
Certains avancent même que le problème serait indécidable.
Le mathématicien hongrois Paul Erdős (1913-1996) célèbre pour ses conjectures (voir conjecture de Erdos-Straus) a dit à propos de la conjecture de Syracuse :
«les mathématiques ne sont pas encore prêtes pour de tels problèmes»
📜 Histoire et anecdotes
C'est en 1928 que le mathématicien allemand Lothar Collatz (1910-1990) invente le problème \(3x+1\) et le présente dans ses séminaires.
Lothar Collatz (1910-1990)
En 1952, lors d'une visite à Hambourg, Collatz expliqua son problème à Helmut Hasse (1898-1979), un des plus grands algébristes allemands de son époque.
Hasse propose alors le problème à ses collègues de l'université de Syracuse dans l'Etat de New York : la suite de Collatz prend alors le nom de « suite de Syracuse ».
Helmut Hasse (1898-1979)
Entre temps, le mathématicien polonais Stanislas Ulam (1909-1984) diffuse le problème, un peu par jeu, dans le Laboratoire national de Los Alamos.
Stanislas Ulam (1909-1984)
Dans les années 1960, le problème est repris par le mathématicien Shizuo Kakutani qui le propage dans les universités de Yale et de Chicago.
Cette conjecture intrigua tant les mathématiciens durant les années 1960, qu'une plaisanterie courut selon laquelle ce problème faisait partie d'un complot soviétique cherchant à perturber les chercheurs américains pendant la guerre froide.
Pour résumer :
- Formulée par Lothar Collatz en 1928.
- Relayée par Helmut Hasse à l'université de Syracuse (d'où le nom !).
- Popularisée par Stanislas Ulam au laboratoire de Los Alamos.
- Une blague des années 60 disait que ce problème était un complot soviétique pour occuper inutilement les mathématiciens occidentaux !
📊 Analyse graphique de la suite de Syracuse
La conjecture affirme que, pour tout \(N=u_0 > 0\) , il existe un indice \(n \) tel que \(u_n = 1\).
L'observation graphique de la suite pour N = 50 et pour N = 2000 montre que la suite peut s'élever assez haut avant de retomber.
Les graphiques font penser à la chute chaotique qui a donné naissance à un vocabulaire imagé associé à la suite, on parlera du vol de la suite.
On définit alors :
- Le temps de vol: c'est le plus petit indice n tel que \(u_n = 1\).
- L'altitude maximale : c'est la valeur maximale de la suite.
Par exemple pour :
- La suite de Syracuse N = 50 : Temps de vol = 24 / Altitude maximale = 88
- La suite de Syracuse N = 2 000 : Temps de vol = 112 / Altitude maximale = 9 232
Voici plusieurs algorithmes
- Algorithme 1
On entre N => Calcul des termes de la suite, du temps de vol, de l'altitude maximale et on visualise le graphique. - Algorithme 2
On entre j => Calcul du temps de vol et de l'altitude max pour chaque suite de Syracuse de N = 2 à N = j.
Les données de l'Algorithme 2 pour J = 2000 : toutes les données
***Algorithme lancé***
Entrer l : 2000
Suite N = 2 : Temps vol = 1 / et Altitude max = 1
Suite N = 3 : Temps vol = 7 / et Altitude max = 16
Suite N = 4 : Temps vol = 2 / et Altitude max = 4
Suite N = 5 : Temps vol = 5 / et Altitude max = 16
Suite N = 6 : Temps vol = 8 / et Altitude max = 16
Suite N = 7 : Temps vol = 16 / et Altitude max = 52
Suite N = 8 : Temps vol = 3 / et Altitude max = 8
Suite N = 9 : Temps vol = 19 / et Altitude max = 52
Suite N = 10 : Temps vol = 6 / et Altitude max = 16
[...]
Suite N = 1999 : Temps vol = 50 / et Altitude max = 20248
Suite N = 2000 : Temps vol = 112 / et Altitude max = 9232
***Algorithme terminé***
📈 Records et comportements extrêmes
Certains entiers produisent des suites exceptionnellement longues ou qui s'élèvent très haut avant de retomber.
- Suite N = 27 : 111 étapes, altitude max = 9232
- Suite N = 6171 : 261 étapes, altitude = 8 153 620
- Suite N = 10971 : 267 étapes, altitude = 27 114 424
- Suite N = 626331 : 508 étapes, altitude ≈ 24 milliards
On obtient les résultat suivants, ne sont affiché que les suites qui ont un temps de vol supérieur ou égal aux précédentes :
- Suite N = 2 : Temps vol = 1 / et Altitude max = 1
- Suite N = 3 : Temps vol = 7 / et Altitude max = 16
- Suite N = 6 : Temps vol = 8 / et Altitude max = 16
- Suite N = 7 : Temps vol = 16 / et Altitude max = 52
- Suite N = 9 : Temps vol = 19 / et Altitude max = 52
- Suite N = 18 : Temps vol = 20 / et Altitude max = 160
- Suite N = 19 : Temps vol = 20 / et Altitude max = 160
- Suite N = 25 : Temps vol = 23 / et Altitude max = 160
- Suite N = 27 : Temps vol = 111 / et Altitude max = 9232
- Suite N = 54 : Temps vol = 112 / et Altitude max = 9232
- Suite N = 55 : Temps vol = 112 / et Altitude max = 9232
- Suite N = 73 : Temps vol = 115 / et Altitude max = 9232
- Suite N = 97 : Temps vol = 118 / et Altitude max = 9232
- Suite N = 129 : Temps vol = 121 / et Altitude max = 9232
- Suite N = 171 : Temps vol = 124 / et Altitude max = 9232
- Suite N = 231 : Temps vol = 127 / et Altitude max = 9232
- Suite N = 235 : Temps vol = 127 / et Altitude max = 9232
- Suite N = 313 : Temps vol = 130 / et Altitude max = 13120
- Suite N = 327 : Temps vol = 143 / et Altitude max = 13120
- Suite N = 649 : Temps vol = 144 / et Altitude max = 41524
- Suite N = 654 : Temps vol = 144 / et Altitude max = 41524
- Suite N = 655 : Temps vol = 144 / et Altitude max = 41524
- Suite N = 667 : Temps vol = 144 / et Altitude max = 41524
- Suite N = 703 : Temps vol = 170 / et Altitude max = 250504
- Suite N = 871 : Temps vol = 178 / et Altitude max = 250504
- Suite N = 1161 : Temps vol = 181 / et Altitude max = 250504
- Suite N = 2223 : Temps vol = 182 / et Altitude max = 1276936
- Suite N = 2322 : Temps vol = 182 / et Altitude max = 1276936
- Suite N = 2323 : Temps vol = 182 / et Altitude max = 1276936
- Suite N = 2463 : Temps vol = 208 / et Altitude max = 1276936
- Suite N = 2919 : Temps vol = 216 / et Altitude max = 1276936
- Suite N = 3711 : Temps vol = 237 / et Altitude max = 1276936
- Suite N = 6171 : Temps vol = 261 / et Altitude max = 8153620
- Suite N = 10971 : Temps vol = 267 / et Altitude max = 27114424
- Suite N = 13255 : Temps vol = 275 / et Altitude max = 27114424
- Suite N = 17647 : Temps vol = 278 / et Altitude max = 27114424
- Suite N = 17673 : Temps vol = 278 / et Altitude max = 27114424
- Suite N = 23529 : Temps vol = 281 / et Altitude max = 50143264
- Suite N = 26623 : Temps vol = 307 / et Altitude max = 1.0635802e+8
- Suite N = 34239 : Temps vol = 310 / et Altitude max = 1.2101286e+8
- Suite N = 35497 : Temps vol = 310 / et Altitude max = 1.2101286e+8
- Suite N = 35655 : Temps vol = 323 / et Altitude max = 1.2101286e+8
- Suite N = 52527 : Temps vol = 339 / et Altitude max = 1.2101286e+8
- Suite N = 77031 : Temps vol = 350 / et Altitude max = 5.9327915e+8
- Suite N = 106239 : Temps vol = 353 / et Altitude max = 1.5708247e+9
- Suite N = 142587 : Temps vol = 374 / et Altitude max = 2.7983234e+9
- Suite N = 156159 : Temps vol = 382 / et Altitude max = 2.7983234e+9
- Suite N = 216367 : Temps vol = 385 / et Altitude max = 1.7202378e+10
- Suite N = 230631 : Temps vol = 442 / et Altitude max = 1.7202378e+10
- Suite N = 410011 : Temps vol = 448 / et Altitude max = 2.4648078e+10
- Suite N = 511935 : Temps vol = 469 / et Altitude max = 2.4648078e+10
- Suite N = 626331 : Temps vol = 508 / et Altitude max = 2.4648078e+10
Articles Connexes
- Une video : https://youtu.be/om4n9ixip7g?feature=shared