Suites de Syracuse :
Une suite de Syracuse est 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 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2… C'est ce qu'on appelle la suite de Syracuse du nombre 14.
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.
Si l'on était parti d'un autre entier que 14, en lui appliquant les mêmes règles, on aurait obtenu une suite de nombres différente. 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, puis au cycle trivial.
La conjecture de Syracuse est aussi appelée conjecture de Collatz, conjecture d'Ulam, conjecture tchèque ou problème 3x+1, c'est l'hypothèse mathématique selon laquelle la suite de Syracuse de tout entier strictement positif atteint 1.
Formulation mathématique des nombres impairs :
Tout nombre impair x entier strictement positif peut être représenté par l'une des deux formules suivantes utilisant deux variables entières a et b :
- ((3*a-2)*2^(2*b)-1)/3 avec a entier impair > 0 et b entier > 0.
- ((3*a-1)*2^(2*b-1)-1)/3 avec a entier pair > 0 et b entier > 0.
Démonstration :
Soit x impair > 0 on a x = 3*x/3 = ((3*x+1)-1)/3 et 3*x+1 est pair puisque x est impair.
3*x+1 pair est donc le produit d'un nombre impair y par une puissance de 2.
3*x+1 est 1 modulo 3.
Les puissances de 2 paires 2^(2*b) sont 1 modulo 3.
Les puissances de 2 impaires 2^(2*b-1) sont -1 modulo 3.
Si la puissance de 2 est paire y doit être 1 modulo 3 soit y impair = 3*a-2 et a impair > 0.
Si la puissance de 2 est impaire y doit être -1 modulo 3 soit y impair = 3*a-1 et a pair > 0.
Donc x est bien égal à ((3*a-2)*2^(2*b)-1)/3 avec a impair > 0 et b >0
ou égal à ((3*a-1)*2^(2*b-1)-1)/3 avec a pair > 0 et b >0.
Définition de le table de Syracuse :
La première colonne d'indice zéro contient les nombres impairs y plus grand que zéro non multiple de 3 dans l'ordre naturel d'occurrence : 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, ...
Les colonnes d'indice i > 0 contiennent (y*2^(2*i)-1)/3 si y est 1 modulo 3 ou (y*2^(2*i-1)-1)/3 si y est -1 modulo 3.
Le tableau commence par :
1, 1, 5, 21, 85, 341, 1365, ....
5, 3, 13, 53, 213, 853, 3413, ....
7, 9, 37, 149, 597, 2389, 9557, ....
11, 29, 117, 469, 1877, 7509, 30037, ....
13, 17, 69, 277, 1109, 4437, 17749, ....
17, 11, 45, 181, 725, 2901, 11605, ....
Les propriétés remarquables de la table de Syracuse :
Tout nombre impair strictement positif non multiple de 3 est présent une seule fois colonne 0.
Tout nombre impair strictement positif non multiple de 3 est présent une seule fois dans les colonnes d'indice > 0.
Tout nombre impair strictement positif est présent une seule fois dans les colonnes d'indice > 0.
Tous les nombres d'une même ligne d'indice de colonne > 0 ont tous le même successeur direct dans une suite de Syracuse et ce nombre est celui colonne 0 dans la ligne.
Seul le nombre impair 1 est présent deux fois dans la première ligne colonne 0 et colonne 1 cycle trivial oblige puisque 1 doit être son propre successeur impair.
Comme tous les nombres impairs d'une même ligne avec indice de colonne > 0 ont tous le même successeur (en colonne zéro de la ligne) et que ce successeur est unique il est impossible de revenir à la même ligne après l'avoir quittée sauf si d'une ligne d'indice > 1 on arrive à la première ligne pour atteindre le cycle trivial.
Donc une suite de Syracuse ne peut que se terminer par 1 ou diverger.
La suite ne peut diverger car il est évident que en partant de 1 on peut construire toute suite de Syracuse inverse et que chacune de ces suites vont diverger.
D'où la preuve de la validité de la conjecture.
-----