La conjecture de Syracuse

Prenez un entier positif ; s’il est pair, divisez-le par 2 ; s’il est impair, multipliez-le par 3 et ajoutez lui 1… Réitérez ce processus sur plusieurs exemples : que semble-t-il se passer ?

Partons de l’entier 7, et regardons la suite alors construite : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1…. Cette suite devient cyclique, puisque l’obtention de la valeur 1 fait « boucler » indéfiniment l’algorithme.

On conjecture que l’on finit toujours par trouver la valeur « 1 » au fil des calculs quel que soit l’entier de départ… C’est la « conjecture de Syracuse » (encore appelée « problème 3n+1 »)… qui attend toujours une preuve !

Nous sommes au début des années 1930, Lothar Collatz, un étudiant de l’université de Hambourg, s’intéresse à la théorie des nombres et à la théorie des graphes.

Il part d’un entier positif quelconque et lui fait subir des transformations itératives (voir l’encadré « la conjecture originelle de Collatz »), trace les graphes associés et se pose des questions qui hantent encore les nuits de bien des chercheurs !

Un problème aux mille visages

C’est probablement Helmut Hasse, un ami de Collatz, qui a largement diffusé le problème 3n+1, qui porte aussi le nom d’« algorithme de Hasse ».

Pendant une visite à l’université de Syracuse (proche de New York, rien à voir avec le port Sicilien ! ) dans les années 50, Hasse diffuse le problème qui a un grand succès, il propose alors de le baptiser « problème de Syracuse ».

Le mathématicien Polonais Stanislas Ulam, qui travaille, pendant la seconde guerre mondiale, à l’université de Los Alamos, fait circuler l’algorithme qui devient bien sûr le « problème de Ulam ».

10 années passent et S. Kakutani s’intéresse au problème, le répand dans plusieurs universités américaines (Yale, Chicago…), la conjecture prend alors le nom de « problème de Kakutani ».

À chaque fois, le problème absorbe l’énergie des mathématiciens qui s’y frottent. À tel point, qu’à l’époque une blague circulait, affirmant que le problème faisait partie d’une conspiration visant à ralentir la recherche mathématique aux États-Unis !

Beaucoup d’encre a coulé, et coulera sans doute encore, autour de ce problème, si bien qu’un vocabulaire métaphorique s’est construit comme souvent en mathématiques.

Reprenons l’exemple initial de l’entier 7. On appellera la suite (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1) la trajectoire ou le vol de 7. Chaque entier de cette suite est une étape du vol, 52 est l’altitude maximale de la trajectoire. La durée d’un vol (16, ici) est le nombre d’étapes nécessaires avant l’apparition du premier ‘1’ (s’il apparaît bien sûr !).

On peut aussi définir la durée du vol en altitude de l’entier 7 comme le nombre d’étapes entre le début du vol et le moment où il passe sous la valeur de départ, 11 dans notre exemple (attention, si la conjecture est fausse, ces durées peuvent être infinies).

Le facteur d’expansion est l’altitude maximale divisée par l’entier de départ (52/7 dans notre exemple).

Voici quelques exemples de comportements de l’algorithme 3n+1 sur des entiers particuliers :

Entier initial	durée	Vol en altitude	Altitude maximale	Facteur d’expansion
7	16	11	52	»7,43
32	5	1	32	1
27	111	96	9232	»341,93
97	118	3	9232	»95,18
	332	3	3377699720527876	3
871	178	57	190996	»219.28
703	170	132	250504	»356.34
100759293214567	1820	166	1180174841128253392	»11712.81

On peut vérifier facilement que, pour les entiers inférieurs à 100, 27 est celui qui donne la plus grande altitude maximale ainsi que le vol en altitude le plus long, 97 fournit la meilleure durée de vol.

Pour les entiers inférieurs à 1000, les champions sont 703 et 871.

Pour les entiers inférieurs à 100000, essayez donc de tester quelques algorithmes (n’hésitez pas à nous les faire parvenir) pour retrouver 77671, 35655 et 77031... et tant qu’à faire, poussez la machine un peu plus loin, qui sait ?

Passons en revue les records actuels (qui sont sans doute déjà dépassés à la parution de cet article) :

- La conjecture a été vérifiée pour tous les entiers inférieurs à 10¹⁵.

- Le record de l’altitude maximale est détenu (pour le moment) par 10709980568908647 qui atteint l’altitude 350589187937078188831873920282244.

- Le record de la trajectoire la plus longue est celle du vol de 1256651665537537 (1865 étapes).

- La meilleure durée en altitude appartient, jusqu’à nouvelle découverte, à 1008932249296231 (1445 étapes en altitude).

Riche de ce nouveau vocabulaire, le problème peut s’énoncer de multiples façons :

Pour tout entier naturel n :

1. Tout vol a une durée finie.

2. Tout vol est de durée en altitude finie.

3. Le nombre d’étapes paires est fini.

On peut facilement démontrer que tous ces énoncés sont équivalents.

(Par exemple, on peut justifier par récurrence que, si le vol en altitude de l’entier n a une durée finie, alors cet entier vérifie la conjecture).

La conjecture peut être démontrée pour une infinité d’entiers.

Considérons la division Euclidienne d’un entier naturel n quelconque par 4 (dont le reste ne peut-être que 0,1,2 ou 3) :

En fait, nous venons de démontrer que 75% des entiers vérifient la conjecture de Syracuse ; par des méthodes similaires, on peut même aller beaucoup plus loin, ne laissant de côté que 2 ou 3 % des entiers…

On peut aussi avoir une approche statistique de l’algorithme. Il y a autant d’entiers pairs que d’entiers impairs dans l’ensemble des entiers naturels, sachant qu’un entier pair est divisé par 2, qu’un entier impair donne naissance à un entier pair (qui sera alors divisé par 2), on peut estimer qu’un entier donné est, en moyenne, multiplié par 3/4 à chaque itération (on « tombe » deux fois plus souvent sur une étape paire, que sur une étape impaire). Ce résultat tendrait aussi à confirmer la conjecture.

Finalement, beaucoup des résultats que nous venons d’énoncer nous poussent à croire que la conjecture deviendrait bien un théorème… Cependant, méfiance, il suffirait qu’un unique entier ne vérifie pas la propriété pour que tout s’effondre !

J. Conway nous fournit une raison supplémentaire de rester prudent : il a réussi à démontrer qu’une simple généralisation de la conjecture était algorithmiquement indécidable (voir l’encadré « Indécidabilité d’une généralisation »).

Alors tout ce travail pour rien ?

Non, bien sûr. Même si ce problème est indécidable, les avancées qu’il a suscitées autant dans la théorie des nombres que dans d’autres domaines des mathématiques, ne sont pas négligeables.

Peut-être que, comme le disait Paul Erdös, « Les Mathématiques ne sont pas encore prêtes pour de tels problèmes ».

ERIC MERCIER

La conjecture originelle de Collatz.

On trouve, dans les notes de Collatz datées du 1 juillet 1932, un problème similaire à la conjecture de Syracuse, aujourd’hui appelé « conjecture originelle de Collatz ».

Si n est un multiple de 3, on le multiplie par 2 puis le divise par 3.

Si n a pour reste 1 dans la division Euclidienne par 3, on le multiplie par 4, lui retranche 1 et divise le tout par 3,

Si n a pour reste 2 dans la même division, on le multiplie par 4, lui ajoute 1 et divise le tout par 3.

Ce qui revient à considérer la fonction :

La question est de connaître la nature de la suite obtenue en itérant ces transformations sur un entier naturel quelconque. La suite diverge-t-elle, devient elle cyclique… ?

Pour les entiers 1,2,3,4,5,6,7 et 9, on vérifie sans trop de peine que les suites deviennent cycliques sur le modèle (4,5,7,9,6,4,5,7,9,6,4...).

Une question, encore ouverte aujourd’hui, est celle de l’avenir de la suite commençant tout simplement par 8 ! Les 50 premiers termes de la suite engendrée par 8 sont [8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767] finit-elle par boucler ou diverge-t-elle vers l’infini ? Avis aux amateurs…

ENCART : Le vol de l’entier 7 a une durée de 16 étapes, l’altitude maximale atteinte est 52. Le vol en altitude est de 11 étapes

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

ENCART : Un problème - deux énoncés.

Un autre énoncé de l’algorithme parfois utilisé aujourd’hui (légèrement différent de l’énoncé de l’article) est le suivant :

Si l’entier n est pair, on le divise par 2.

Si n est impair, on le multiplie par 3, lui ajoute 1 puis on divise le résultat par 2.

Ce qui revient à l’utilisation de la fonction S définie par :

Cet énoncé permet de réduire le nombre d’étapes, puisque 3n+1 est toujours pair lorsque n est impair. Attention alors, certains des records (en durée, en vol en altitude, en altitude maximale), ne sont plus les mêmes qu’avec l’énoncé utilisé ici.

ENCART : Des liens

http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html : une documentation très riche de Jeffrey Lagarias.

http://personal.computrain.nl/eric/wondrous/index.html : Quelques détails et l’état des records…

http://www.inesca.pt/~tos/3x+1.html

ENCART : Indécidabilité d’une généralisation

Au lieu de s’intéresser au reste de la division Euclidienne d’un entier par 2, J.H. Conway considère le reste de la division par un entier p (les restes possibles sont 0,1,2,…,p-1).

Il propose alors p formules à appliquer itérativement suivant les restes obtenus. En généralisant la conjecture de Syracuse à ce type d’algorithme, Conway a démontré que l’on arrivait à un problème indécidable.