Les suites de Syracuse sont des suites mathématiques d'entiers naturels, c'est-à-dire d'entiers positifs, très connues et très étudiées par les mathématiciens et ce depuis un peu moins d'un siècle. Le problème a été découvert en 1928 alors que Lothar Collatz, un mathématicien allemand, s'intéresse aux itérations dans les nombres entiers. À cette époque, ce problème était encore appelé "problème 3x+1". Par la suite, dans les années 50 et 60, le problème s'est diffusé un peu partout dans le monde et a pris le nom sous lequel on le connait actuellement.
Ce sont des suites récursives assez originales. Le principe, très simple à comprendre, est défini de la manière suivante :
On part d'une valeur entière positive n plus grande que zéro.
Si cette valeur n est paire alors la valeur suivante sera n/2.
Sinon, la valeur suivante sera 3 imes n + 1.
La suite de Syracuse obtenue en partant de n est appelée "suite de Syracuse du nombre n".
Si je pars de la valeur 7, j'obtiens logiquement la suite suivante :
7 ightarrow 22 ightarrow 11 ightarrow 34 ightarrow 17 ightarrow 52 ightarrow 26 ightarrow 13 ightarrow 40 ightarrow 20 ightarrow 10 ightarrow 5 ightarrow 16 ightarrow 8 ightarrow 4 ightarrow 2 ightarrow 1 ightarrow 4 ightarrow 2 ightarrow 1 ightarrow 4 ightarrow 2 ightarrow 1 ...
On remarque vite qu'il y a quelque chose de remarquable à cette suite : dés qu'on arrive sur 1, le cycle de longueur trois 4 ightarrow 2 ightarrow 1, appelé "cycle trivial" ("trivial" signifiant "banal, ordinaire, commun, etc."), se forme. En effet, en se référant à la définition des suites de Syracuse, la valeur suivant 1 est 3 imes 1 + 1 donc 4. Or, 4 est pair, donc la valeur suivante sera 2 et rebelote, comme 2 est pair, on retombe sur 1 et le tout recommence à zéro. En général, quand on expose les différentes valeurs d'une suite de Syracuse, on s'arrête à 1 ou alors on écrit \bar{4 ightarrow 2 ightarrow 1}.
Mais en admettant ceci, je conjecture que toutes les suites de Syracuse arrivent à 1. Or, vous vous en doutez bien, il existe une infinité de suites de Syracuse car on peut partir de n'importe quelle valeur entière naturelle, et il en existe une infinité. Ce qu'il y a de bien embêtant pour les mathématiciens là dedans, c'est que jusqu'à présent, personne n'a réussi à démontrer que toute suite de Syracuse tombe à 1. On admet ceci, on conjecture et cette conjecture porte justement un nom, c'est la conjecture de Syracuse.
Tout ce qu'on est en mesure de faire, et qu'on a déjà bien fait d'ailleurs, c'est de tester différentes valeurs et de constater que pour ces valeurs, on tombe effectivement à 1. En janvier 2008, on a ainsi vérifié la conjecture de Syracuse pour toute valeur inférieure à 2^{62}. Mais les mathématiciens ne se sentent toujours pas à l'abri d'un cas non-trivial. En effet, ils n'excluent pas la possibilité qu'une suite de Syracuse puisse soit diverger vers l'infini, soit tomber dans un autre cycle.
Les suites de Syracuse possèdent encore une autre particularité. On remarque qu'en partant de n'importe quelle valeur, la courbe représentant la suite commence par croitre avant de retomber "à la manière d'une feuille emportée par le vent". On parle du "vol de la suite" pour désigner la courbe de la suite sur un graphique. Le "temps de vol" de la suite de Syracuse du nombre n désigne le nombre de valeurs de cette suite avant de tomber sur 1, 1inclue, n exclue. "L'altitude maximale" désigne la plus grande valeur atteinte.
On se rend compte que si l'on a un nombre n impair, alors 3 imes n + 1 sera forcément un nombre pair. On peut donc anticiper en "compressant" le nombre de valeurs d'une suite de Syracuse en admettant que si n est impair, alors la valeur suivante sera \frac{3 imes n + 1}{2}. On appelle ceci "suite de Syracuse compressée" et en admettant la conjecture, le cycle se répétant toujours serait \bar{2 ightarrow 1}.
Voici le graphe de la suite de Syracuse compressée du nombre 15 : lien.