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.
La suite de Syracuse
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. $$
La conjecture de Syracuse
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 du problème
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.
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 ».
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. 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.
Les valeurs remarquables des suites 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é***
Suites de Syracuse et record de temps de vol
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
