La conjecture de Syracuse

Ce que dit la conjecture

On choisit un entier de départ $u_0 \geq 1$ et l’on construit la suite définie par

La conjecture de Syracuse affirme que, quel que soit l’entier de départ, la suite finit par atteindre la valeur 1. Une fois en 1, elle tourne indéfiniment dans le cycle $1 \to 4 \to 2 \to 1$.

C’est une conjecture : un énoncé que l’on croit vrai, mais qui n’a jamais été démontré. Il a été vérifié par ordinateur pour tous les entiers de départ inférieurs à $2^{71}$, environ $2{,}36 \times 10^{21}$, mais une vérification, aussi longue soit-elle, ne remplace pas une preuve : un contre-exemple pourrait exister plus loin.

• $u_0$ : l’entier de départ, au moins égal à 1 (avec $u_0 = 0$, la suite reste bloquée sur 0).
• $u_n$ : le terme obtenu après $n$ étapes.
• pair : divisible par 2 ; impair : non divisible par 2.
• Le temps de vol est le nombre d’étapes nécessaires pour atteindre 1 ; l’altitude maximale est la plus grande valeur rencontrée en chemin.

Un contre-exemple à la conjecture serait soit une suite qui grandit sans jamais redescendre, soit une suite qui entre dans un autre cycle que $1 \to 4 \to 2 \to 1$. Aucun des deux n’a jamais été trouvé.

Le problème porte aussi les noms de problème $3n + 1$, conjecture de Collatz, d’Ulam ou de Kakutani.

Un exemple

Partons de $u_0 = 6$ :

6 est pair, on le divise par 2 et l’on obtient 3. 3 est impair : $3 \times 3 + 1 = 10$. 10 est pair : 5. Puis $3 \times 5 + 1 = 16$, et 16 étant une puissance de 2, on redescend 8, 4, 2, 1. Le temps de vol est de 8 étapes et l’altitude maximale vaut 16.

Le nombre voisin 7 se comporte déjà autrement :

soit 16 étapes, avec une altitude maximale de 52.

Le cas le plus célèbre est $u_0 = 27$. La suite monte, redescend, remonte pendant longtemps : elle atteint 9 232 à l’étape 77 et n’arrive à 1 qu’au bout de 111 étapes, après être passée par 41 nombres impairs. Parmi les entiers de départ inférieurs à un million, le temps de vol le plus long est celui de 837 799, avec 524 étapes ; au-dessous de dix millions, c’est 8 400 511, avec 685 étapes.

Les programmes de l’atelier ont recalculé tout cela : les suites de tous les entiers de 1 à 10 000 000 atteignent 1 (c’est une vérification sur cet intervalle seulement), la plus haute valeur rencontrée étant 60 342 610 919 632. Les temps de vol de 1 à 72, les records de temps de vol jusqu’à 837 799 et les altitudes maximales de 1 à 27 ont été comparés aux tables de l’encyclopédie en ligne des suites d’entiers (OEIS), et les deux records cités plus haut retrouvés.

Pourquoi on y croit, sans preuve

La démonstration de la conjecture est inconnue : personne ne sait aujourd’hui prouver qu’elle est vraie, ni qu’elle est fausse. On peut seulement expliquer pourquoi la plupart des mathématiciens pensent qu’elle est vraie, et ce que l’on sait démontrer.

Un argument de probabilité, qui n’est pas une preuve. Quand $u_n$ est impair, $3u_n + 1$ est toujours pair : l’étape suivante est donc une division par 2. Si l’on imagine que les nombres obtenus sont pairs ou impairs « au hasard », un nombre impair est multiplié par 3, puis divisé une fois par 2 avec probabilité $\frac{1}{2}$, deux fois avec probabilité $\frac{1}{4}$, et ainsi de suite. En moyenne, d’un nombre impair au suivant, la valeur est multipliée par $\frac{3}{4}$ : la suite aurait tendance à descendre. Mais les termes de la suite ne sont pas tirés au hasard ; ce raisonnement n’exclut ni une suite exceptionnelle qui monterait toujours, ni un cycle caché.

Ce que l’on sait démontrer.

• Pour vérifier la conjecture jusqu’à une borne $N$, il suffit de montrer que chaque entier $u_0 \geq 2$ inférieur ou égal à $N$ finit par passer au-dessous de lui-même. En effet, le plus petit contre-exemple éventuel ne pourrait pas tomber sur un nombre plus petit, puisque celui-là atteint 1. C’est ainsi que procèdent les vérifications par ordinateur, et celle de l’atelier.
• Riho Terras a montré dans les années 1970 que presque tous les entiers, au sens de la densité, finissent par passer au-dessous de leur valeur de départ.
• En 2019, Terence Tao a démontré que presque toutes les suites (en un sens de densité plus fin) descendent au-dessous de n’importe quelle fonction de $u_0$ qui tend vers l’infini, aussi lentement soit-elle. C’est l’un des résultats les plus forts obtenus sur le problème, mais « presque toutes » ne veut pas dire « toutes » : la conjecture reste ouverte.

La règle exacte compte. Une variante en apparence anodine change tout. Avec $3u_n - 1$ au lieu de $3u_n + 1$, la suite partant de 5 tourne en rond : $5 \to 14 \to 7 \to 20 \to 10 \to 5$, sans jamais atteindre 1. Avec $5u_n + 1$, la suite partant de 13 entre elle aussi dans un cycle : $13 \to 66 \to 33 \to 166 \to 83 \to 416 \to 208 \to 104 \to 52 \to 26 \to 13$. L’atelier contrôle ces deux contre-exemples par le calcul.

Un peu d’histoire

Le problème est attribué au mathématicien allemand Lothar Collatz, qui s’intéressait dès les années 1930 aux itérations de fonctions sur les entiers ; on date souvent son idée de 1937. Il n’a pas été publié tout de suite : il a d’abord circulé de bouche à oreille. Selon le mathématicien Jeffrey Lagarias, auteur d’une synthèse de référence sur le sujet, Helmut Hasse l’a fait connaître dans les années 1950, notamment lors d’un passage à l’université de Syracuse, dans l’État de New York, d’où le nom de « problème de Syracuse ». Stanislaw Ulam l’a diffusé à Los Alamos et Shizuo Kakutani à Yale et à Chicago dans les années 1960. Les premières publications datent des années 1970.

Depuis, les vérifications par ordinateur n’ont cessé de reculer la borne. La plus récente, publiée en 2025 par David Barina dans The Journal of Supercomputing, couvre tous les entiers de départ inférieurs à $2^{71}$.

Ce que montre l’affiche

Le dessin est un arbre calculé à partir des suites de tous les entiers de départ de 1 à 6 000. Chaque suite est tracée à l’envers, en partant de 1 (le point à la base) : à chaque terme, le trait avance d’un pas et tourne d’un petit angle vers la gauche si le nombre atteint est pair, d’un angle double vers la droite s’il est impair. Comme deux suites qui se rejoignent ont ensuite le même parcours, leurs tracés se confondent : chacun des 12 912 nombres rencontrés est placé une seule fois, et l’ensemble forme une sorte de plume. Les traits sont d’autant plus épais que davantage de trajectoires y passent, et leur couleur change avec la distance à 1. Sous la formule, l’affiche rappelle le trajet de 27 : 9 232 à l’étape 77, puis 1 à l’étape 111. L’affiche existe en quatre styles : Papier, Nuit, Bauhaus et Tableau noir.

Pour aller plus loin

• La conjecture de Goldbach, autre énoncé sur les entiers, simple à dire et jamais démontré.
• Les nombres premiers et le grand théorème de Fermat, un problème resté ouvert plus de trois siècles avant d’être résolu.
• Les suites arithmétiques et géométriques, des suites définies elles aussi par une relation de récurrence.

Sources : Conjecture de Syracuse (Wikipédia) (nouvel onglet), Collatz conjecture (Wikipedia) (nouvel onglet), Collatz Problem (MathWorld) (nouvel onglet), suite A006577 (OEIS) (nouvel onglet), suite A006877 (OEIS) (nouvel onglet), D. Barina, Improved verification limit for the convergence of the Collatz conjecture (2025) (nouvel onglet).