Sciences · Mathématiques
La conjecture de Syracuse
Partez d’un entier : s’il est pair, divisez-le par 2 ; s’il est impair, multipliez-le par 3 et ajoutez 1. La conjecture de Syracuse affirme qu’on finit toujours par atteindre 1, quel que soit le départ. Elle n’est pas démontrée.
Mis à jour le 4 min de lecture
Une règle qu’un enfant de dix ans peut appliquer, et un problème que les plus grands mathématiciens n’ont pas su résoudre. Formulée dans les années 1930 par l’Allemand Lothar Collatz, la conjecture a circulé ensuite sous de nombreux noms : problème 3x + 1, conjecture de Collatz, d’Ulam, de Kakutani, ou de Syracuse — d’après l’université de Syracuse (État de New York), où elle a été popularisée. Le mathématicien Paul Erdős aurait estimé que les mathématiques n’étaient pas encore prêtes pour ce genre de problème.
Des exemples
Le vocabulaire du « vol »
Les mathématiciens ont imaginé une image aéronautique : la suite est un vol, ses valeurs des altitudes.
| Terme | Signification | Pour n = 7 |
|---|---|---|
| Temps de vol | Nombre d’étapes pour atteindre 1 | 16 |
| Altitude maximale | Plus grande valeur atteinte | 52 |
| Temps de vol en altitude | Nombre d’étapes avant de passer sous la valeur de départ | 11 |
Pourquoi le problème est-il si résistant ?
Le comportement de la suite mélange deux opérations qui n’ont rien à voir : diviser par 2 et multiplier par 3. La parité de chaque terme semble imprévisible.
Un argument heuristique rend la conjecture plausible : après une étape impaire (3n + 1, toujours pair), on divise au moins une fois par 2. En moyenne, chaque « montée » est suivie de suffisamment de « descentes » pour que la suite se contracte d’un facteur d’environ 3/4 par cycle. Mais une moyenne ne prouve rien pour chaque nombre : il faudrait exclure deux scénarios, une suite qui grandit indéfiniment et un autre cycle que 1 → 4 → 2 → 1.
Ce que l’on sait
| Résultat | Détail |
|---|---|
| Vérification informatique | Tous les entiers de départ jusqu’à environ 2⁶⁸ (près de 3 × 10²⁰) atteignent 1 (2020) |
| Cycles | Tout autre cycle devrait compter au moins plusieurs millions de termes |
| Presque tous les entiers | Terence Tao (2019) : pour « presque tous » les n, la suite descend en dessous de toute fonction tendant vers l’infini, aussi lente soit-elle |
| Indécidabilité | John Conway a montré (1972) que des généralisations de ce type de problème sont algorithmiquement indécidables |
Le résultat de Tao est considéré comme l’avancée la plus forte, mais il laisse ouverte la possibilité d’une rare exception. L’interprétation « presque tous » a un sens précis en densité logarithmique : une proportion de nombres de départ tendant vers 100 %.
Les variantes
Avec la règle 3n − 1 (ou en partant d’entiers négatifs), d’autres cycles existent : 5 → 14 → 7 → 20 → 10 → 5. Avec 5n + 1, certaines suites semblent croître sans fin. Cela montre que le cas 3n + 1 est subtil et que la propriété n’est pas « évidente ».
Programmer la suite
C’est un excellent exercice d'algorithme :
- tant que n ≠ 1 : si n est pair,
n ← n / 2, sinonn ← 3n + 1; incrémenter un compteur d’étapes ; - afficher le compteur (temps de vol) et la valeur maximale rencontrée.
Il permet de vérifier soi-même des milliers de départs et d’observer la grande irrégularité des temps de vol. La suite est un bon exemple de suite définie par récurrence (voir les suites numériques) dont on ignore la forme explicite.
Erreurs fréquentes
- Croire qu’une vérification informatique suffit : la conjecture porte sur une infinité de nombres.
- Confondre avec un théorème : rien n’est démontré pour tous les entiers.
- Mal appliquer la règle : pour un impair, c’est
3n + 1, puis on continue avec ce nouveau nombre pair.
Questions fréquentes
La conjecture de Syracuse est-elle démontrée ?
Non. Elle est vérifiée par ordinateur jusqu’à environ 3 × 10²⁰ et Terence Tao a prouvé un résultat valable pour presque tous les entiers, mais aucune preuve complète n’existe.
Pourquoi s’appelle-t-elle conjecture de Syracuse ?
Parce qu’elle a été diffusée à l’université de Syracuse, aux États-Unis, dans les années 1950. Elle est due à Lothar Collatz (années 1930), d’où son autre nom.
Quel nombre a le plus long temps de vol ?
Parmi les nombres inférieurs à 100, c’est 97, avec 118 étapes. Sous 1 000, c’est 871, avec 178 étapes.
Y a-t-il un prix pour la résoudre ?
Des récompenses ont été proposées à diverses époques par des mathématiciens (Erdős, Thwaites) puis par des entreprises, mais elle ne fait pas partie des problèmes du millénaire.