conjecture syracuse ulam
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 :

  1. On part d'un nombre entier plus grand que zéro ;
    1. s'il est pair, on le divise par 2 ;
    2. s'il est impair, on le multiplie par 3 et on ajoute 1.
  2. 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. 

conjecture syracuse cycle trivial

La suite de Syracuse 

La suite \((u_n)\) est définie pour tout entier n par : \(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 n pair} \\3u_n+1 & \text{si n 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

suite syracuse n50

  • La suite de Syracuse N = 2 000  : Temps de vol = 112 / Altitude maximale  = 9 232

suite syracuse n2000

 

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

  1. Suite N = 2 : Temps vol = 1 / et Altitude max = 1
  2. Suite N = 3 : Temps vol = 7 / et Altitude max = 16
  3. Suite N = 6 : Temps vol = 8 / et Altitude max = 16
  4. Suite N = 7 : Temps vol = 16 / et Altitude max = 52
  5. Suite N = 9 : Temps vol = 19 / et Altitude max = 52
  6. Suite N = 18 : Temps vol = 20 / et Altitude max = 160
  7. Suite N = 19 : Temps vol = 20 / et Altitude max = 160
  8. Suite N = 25 : Temps vol = 23 / et Altitude max = 160
  9. Suite N = 27 : Temps vol = 111 / et Altitude max = 9232
  10. Suite N = 54 : Temps vol = 112 / et Altitude max = 9232
  11. Suite N = 55 : Temps vol = 112 / et Altitude max = 9232
  12. Suite N = 73 : Temps vol = 115 / et Altitude max = 9232
  13. Suite N = 97 : Temps vol = 118 / et Altitude max = 9232
  14. Suite N = 129 : Temps vol = 121 / et Altitude max = 9232
  15. Suite N = 171 : Temps vol = 124 / et Altitude max = 9232
  16. Suite N = 231 : Temps vol = 127 / et Altitude max = 9232
  17. Suite N = 235 : Temps vol = 127 / et Altitude max = 9232
  18. Suite N = 313 : Temps vol = 130 / et Altitude max = 13120
  19. Suite N = 327 : Temps vol = 143 / et Altitude max = 13120
  20. Suite N = 649 : Temps vol = 144 / et Altitude max = 41524
  21. Suite N = 654 : Temps vol = 144 / et Altitude max = 41524
  22. Suite N = 655 : Temps vol = 144 / et Altitude max = 41524
  23. Suite N = 667 : Temps vol = 144 / et Altitude max = 41524
  24. Suite N = 703 : Temps vol = 170 / et Altitude max = 250504
  25. Suite N = 871 : Temps vol = 178 / et Altitude max = 250504
  26. Suite N = 1161 : Temps vol = 181 / et Altitude max = 250504
  27. Suite N = 2223 : Temps vol = 182 / et Altitude max = 1276936
  28. Suite N = 2322 : Temps vol = 182 / et Altitude max = 1276936
  29. Suite N = 2323 : Temps vol = 182 / et Altitude max = 1276936
  30. Suite N = 2463 : Temps vol = 208 / et Altitude max = 1276936
  31. Suite N = 2919 : Temps vol = 216 / et Altitude max = 1276936
  32. Suite N = 3711 : Temps vol = 237 / et Altitude max = 1276936
  33. Suite N = 6171 : Temps vol = 261 / et Altitude max = 8153620
  34. Suite N = 10971 : Temps vol = 267 / et Altitude max = 27114424
  35. Suite N = 13255 : Temps vol = 275 / et Altitude max = 27114424
  36. Suite N = 17647 : Temps vol = 278 / et Altitude max = 27114424
  37. Suite N = 17673 : Temps vol = 278 / et Altitude max = 27114424
  38. Suite N = 23529 : Temps vol = 281 / et Altitude max = 50143264
  39. Suite N = 26623 : Temps vol = 307 / et Altitude max = 1.0635802e+8
  40. Suite N = 34239 : Temps vol = 310 / et Altitude max = 1.2101286e+8
  41. Suite N = 35497 : Temps vol = 310 / et Altitude max = 1.2101286e+8
  42. Suite N = 35655 : Temps vol = 323 / et Altitude max = 1.2101286e+8
  43. Suite N = 52527 : Temps vol = 339 / et Altitude max = 1.2101286e+8
  44. Suite N = 77031 : Temps vol = 350 / et Altitude max = 5.9327915e+8
  45. Suite N = 106239 : Temps vol = 353 / et Altitude max = 1.5708247e+9
  46. Suite N = 142587 : Temps vol = 374 / et Altitude max = 2.7983234e+9
  47. Suite N = 156159 : Temps vol = 382 / et Altitude max = 2.7983234e+9
  48. Suite N = 216367 : Temps vol = 385 / et Altitude max = 1.7202378e+10
  49. Suite N = 230631 : Temps vol = 442 / et Altitude max = 1.7202378e+10
  50. Suite N = 410011 : Temps vol = 448 / et Altitude max = 2.4648078e+10
  51. Suite N = 511935 : Temps vol = 469 / et Altitude max = 2.4648078e+10
  52. Suite N = 626331 : Temps vol = 508 / et Altitude max = 2.4648078e+10

Articles Connexes