Le problème 3n+1 : élémentaire mais redoutable (I)
Piste verte Le 13 novembre 2011 Voir les commentaires (23)Lire l'article en
Parmi tous les problèmes mathématiques actuellement non résolus, quel est celui dont l’énoncé est le plus élémentaire ? C’est peut-être bien le problème présenté ici : accessible à tout écolier de 8 ans, il défie les chercheurs depuis des décennies.
Le problème $3n+1$ offre un contraste saisissant : d’un côté il est extrêmement simple à énoncer, de l’autre il semble extrêmement difficile à résoudre. Quel est-il donc ? On définit une règle de transformation sur les nombres entiers 1,2,3,... de la façon suivante : étant donné un entier naturel $n$ quelconque,
- si $n$ est pair, on le divise par 2 ;
- si $n$ est impair, on le multiplie par 3 et on ajoute 1.
Par exemple, appliquée au nombre 14, cette transformation donne 7 ; et appliquée à 7 elle donne 22. On écrira $14 \rightarrow 7$ et $7 \rightarrow 22$ pour résumer, et même $14 \rightarrow 7 \rightarrow 22$ pour faire encore plus court [1].
Plus généralement, on écrira $n \rightarrow m$ pour dire « $n$ va sur $m$ », sous-entendu toujours par cette transformation.
Le problème $3n+1$ est le suivant : partons d’un nombre entier positif quelconque, et appliquons-lui cette transformation de façon répétée. Est-il vrai que l’on finira tôt ou tard par tomber sur 1 ?
Tous les calculs faits à ce jour confirment cette prédiction. Mais voilà, personne depuis des décennies ne sait comment la démontrer, et ce n’est pas faute d’avoir essayé. D’ailleurs, selon le grand Paul Erdös (1913-1996), les mathématiques ne seraient pas encore assez mûres pour espérer résoudre cet innocent petit problème [2].
Un peu de vocabulaire
On appellera transformation de Collatz cette transformation, du nom de son premier inventeur, dans les années 1930 semble-t-il. Et on appellera trajectoire de $n$ la suite obtenue en partant de $n$ et en lui appliquant de façon répétée cette transformation.
Le problème $3n+1$ consiste donc à déterminer s’il est vrai que toute trajectoire atteint 1.
Notons qu’il est aussi connu sous divers autres noms : Collatz, Kakutani, Syracuse, etc.
Trois exemples
Partons d’abord de 1 lui-même. Quelle est sa trajectoire, obtenue par application répétée de ladite transformation ? On obtient la suite
\[
1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots \,.
\]
On constate que l’on retombe effectivement sur 1, à la 3ème étape ; puis la suite $1,4,2$ se répète indéfiniment. On dira que c’est un cycle, en l’occurrence de longueur 3.
Comme second exemple, partons de $n=3$. On obtient la suite
\[
3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots \,.
\]
Là encore on retombe sur 1, à la 7ème étape.
Partant enfin de $n=7$, on obtient la suite
\[
\begin{array}{l}
& 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \\ & \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots
\end{array}
\]
qui tombe sur 1 à la 16ème étape.
A ce stade, le lecteur est vivement encouragé à choisir d’autres entiers de départ et à s’amuser à en calculer les trajectoires. C’est d’ailleurs la meilleure façon de donner vie, dans le confort de son espace mental, à un être mathématique quel qu’il soit : jouer avec, le mettre en situation, le considérer sous toutes ses coutures, expérimenter.
La trajectoire de 27
Certaines trajectoires sont spectaculaires et valent le détour. Celle de $n=27$, par exemple, est une montagne russe qui monte vers des hauteurs inattendues. Mais rien n’y fait, après quelques dizaines d’étapes, vous verrez, elle retombe sur 1.
De nombreuses pages sur Internet permettent de calculer ces trajectoires, par exemple celle-ci [3] ou, en français, celle citée dans l’article de Wikipedia consacré au problème [4].
Le logo
Le logo de cet article représente toutes les trajectoires atteignant 1 en au plus 18 étapes [5]. Une très jolie animation [6] montre sa construction progressive, selon la longueur maximale des trajectoires variant de 1 à 18. Son auteur est Jason Davies, qui a gentiment accepté de me le fournir en vert, bleu et rouge spécialement pour cette série d’articles, et que je remercie beaucoup. On peut contempler ce logo plus en détail en cliquant sur l’image :
Record actuel
C’est un chercheur portugais, Tomás Oliveira e Silva, qui détient depuis 2009 le record de vérification du problème $3n+1$ par ordinateur [7]. Il a vérifié qu’effectivement, la trajectoire de tout nombre entier positif inférieur à $5 \times 10^{18}$, c’est-à-dire à 5 milliards de milliards, retombe bel et bien sur 1. Pour pousser la vérification toujours plus loin, ses calculs reprendront de plus belle sur une plate-forme plus puissante en 2012.
Élémentaire ...
Pour comprendre l’énoncé du problème $3n+1$, on voit qu’il suffit de connaître les nombres entiers, de savoir y distinguer les pairs des impairs, et enfin de maîtriser des opérations arithmétiques simples : additionner 1, multiplier par 3, diviser par 2. Rien de plus. Il est donc accessible à tout enfant de 8 ans normalement scolarisé, qui de plus peut instantanément se mettre à calculer des trajectoires et à en observer l’évolution.
... mais redoutable
Le profil type du problème $3n+1$ est celui d’une fonction simple à définir, mais dont le comportement devient difficile à prédire lorsqu’on l’itère, c’est-à-dire lorsqu’on l’applique de façon répétée. C’est un système dynamique discret [8]. Des centaines de chercheurs, depuis des décennies, ont tenté et tentent encore de résoudre ce problème à l’apparence si anodine. Il en a résulté un grand nombre de publications scientifiques, avec des résultats partiels et des études de problèmes analogues. Mais toujours pas de solution à ce jour.
Par chance, un expert nommé Jeff Lagarias a choisi de créer et de maintenir, sans interruption depuis 1985, une liste commentée de tous les articles consacrés à ce problème [9]. Il vient d’ailleurs de publier un livre très complet sur le sujet, « The Ultimate Challenge : The $3x+1$ Problem » [10].
C’est vexant tout de même, non ? Malgré leur puissance, leur profondeur, leur efficacité, leurs arsenaux conceptuels, leurs trésors d’ingéniosité, les mathématiques butent sur un problème qu’un enfant de 8 ans peut comprendre en quelques instants.
Deux sous-problèmes
Le problème $3n+1$ est un pari sur le comportement à long terme des trajectoires des entiers positifs pour la transformation de Collatz, à savoir que toute trajectoire finit par atteindre 1.
En amont de ce pari spécifique, il est naturel de se demander, en toute généralité, quels sont les comportements possibles à long terme d’une trajectoire quelconque. Eh bien, il n’y a ici que deux possibilités :
- ou bien la trajectoire considérée est plafonnée,
- ou bien elle ne l’est pas.
Dire qu’elle est plafonnée signifie qu’aussi loin qu’on la parcoure, ses termes restent toujours en-dessous d’un certain plafond. C’est le cas par exemple pour la trajectoire de 3, qui reste indéfiniment en-dessous de 16. De même, la trajectoire de 7 est plafonnée par 52, comme on peut le constater ci-dessus. Notons qu’une trajectoire plafonnée contiendra forcément, tôt ou tard, des répétitions. Dans ce cas-là, la trajectoire finit par s’enrouler dans un cycle. On connaît bien le cycle 1,4,2,1, mais y en a-t-il d’autres ?
Par contre, une trajectoire non plafonnée aurait la propriété de filer inexorablement vers l’infini, malgré un inévitable parcours en dents de scie. Autrement dit, en cheminant loin dans la trajectoire, on trouvera forcément un terme plus grand que 100 ; puis plus loin, un autre supérieur à 1.000 ; puis plus loin encore, un autre dépassant 10.000 ; etc. Techniquement parlant, on dirait qu’une telle trajectoire diverge.
Le problème $3n+1$ se réduit donc à deux sous-problèmes :
- Est-il vrai que le seul cycle est le cycle 1,4,2,1 ?
- Est-il vrai qu’il n’y a aucune trajectoire divergente ?
On ne sait résoudre aucun de ces deux sous-problèmes à l’heure actuelle. La solution de l’un ou l’autre serait d’ailleurs considérée, à juste titre, comme un progrès majeur.
Afin de mieux comprendre cette situation, illustrons-la dans des contextes légèrement différents.
Sur les entiers négatifs
Les règles définissant la transformation de Collatz, suivant la parité du nombre considéré, gardent tout leur sens si on les applique aux nombres entiers négatifs. Par exemple, $-1$ est impair, et va donc sur $3 \times (-1)+1$ par la transformation de Collatz, c’est-à-dire sur $-2$. De même, on a $-2 \rightarrow -1$. On observe ainsi, sur les entiers négatifs, un cycle de longueur 2. Or là, surprise, ce n’est pas le seul ! On en connaît même deux autres :
- la trajectoire de $-5$, donnant un cycle de longueur 5 :
- celle de $-17$, donnant un cycle de longueur 18 :
Cette présence de trois cycles différents sur les entiers négatifs [11] rend d’autant plus intéressante la prédiction selon laquelle il n’y aurait qu’un seul cycle sur les entiers positifs.
La variante $5n+1$
Une légère variante de la transformation de Collatz, où l’on remplace $3n+1$ par $5n+1$, permet d’illustrer simultanément les deux sous-problèmes. En fait, pour accélérer un peu le cheminement dans les trajectoires, on remplace $3n+1$ par $(5n+1)/2$ plutôt que par $5n+1$ [12]. Autrement dit, considérons la transformation suivante :
- si $n$ est pair, on le divise par 2, comme avant ;
- mais si $n$ est impair, on l’envoie sur $(5n+1)/2$.
On utilisera le symbole $\succ$ pour dénoter cette nouvelle transformation. Voici par exemple la trajectoire de 1 :
\[1 \succ 3 \succ 8 \succ 4\succ 2\succ 1 \succ \ldots,\]
un joli cycle de longueur 5. Voici un autre cycle, cette fois-ci de longueur 7 :
\[
13 \succ 33 \succ 83 \succ 208 \succ 104 \succ 52 \succ 26 \succ 13 \succ \ldots.
\]
Partons maintenant de $n=7$. Là, un nouveau phénomène se manifeste. En effet, regardons les 16 premiers termes de la trajectoire de 7 :
\[
\begin{array}{ll}
& 7\succ 18\succ 9\succ 23\succ 58\succ 29\succ 73\succ 183\succ 458 \succ 229 \\& \succ 573\succ 1433\succ 3583\succ 8958\succ 4479\succ 11198.
\end{array}
\]
Cela grimpe assez fort. Allons un peu plus loin dans cette trajectoire, jusqu’au 1000ème terme par exemple. On trouve alors
\[
6.857.007.305.798.959.806.990.948.240.228.589.098.703.203.749,
\]
un nombre à 46 chiffres. On continue ? Je remercie beaucoup Jonathan Chappelon qui a bien voulu, pour cet article, pousser le calcul de cette trajectoire jusqu’à son 21 millionième terme. Le nombre obtenu n’est même plus montrable ici : il a plus d’un million de chiffres (exactement 1.016.568) ! Il y a effectivement une très forte présomption que la trajectoire de 7 diverge ; mais personne à ce jour ne sait le démontrer. Pire que cela : on pense que la plupart des trajectoires de cette transformation sont divergentes ; mais personne ne sait prouver qu’il en existe au moins une qui le soit vraiment.
Trajectoires divergentes
Pourquoi donc semble-t-il y avoir des trajectoires divergentes avec $(5n+1)/2$ mais pas avec $3n+1$, ou ce qui revient au même, pas avec $(3n+1)/2$ ? Ce ne sont encore que des observations empiriques, qui demandent à être formellement prouvées ; mais d’où peut bien venir cette différence apparente de comportement ?
Voici une explication intuitive possible. Elle repose sur quelques approximations, une hypothèse osée mais plausible et, en fin de compte, sur le fait que 5/4 est supérieur à 1 alors que 3/4 ne l’est pas.
Cheminons le long de la trajectoire de 7 par exemple, d’abord pour la transformation $\succ$, c’est-à-dire avec $(5n+1)/2.$ Pour passer de chaque terme au suivant, on le multiplie par 1/2 s’il est pair, ou par environ 5/2 s’il est impair. Admettons que, lors de ce cheminement, on rencontre à peu près autant de pairs que d’impairs [13]. Alors, si l’on marche jusqu’au 21 millionième terme par exemple, celui-ci devrait valoir environ
\[
7 \cdot \left(\frac12\right)^{10.500.000} \cdot \left(\frac52\right)^{10.500.000},
\]
c’est-à-dire environ
\[
7 \cdot \left(\frac54\right)^{10.500.000}.
\]
Or 5/4 étant plus grand que 1, ses puissances successives grandissent sans limites. Le nombre ci-dessus compte d’ailleurs 1.017.556 chiffres avant la virgule, ce qui en fait une assez bonne approximation du véridique 21 millionième terme de la trajectoire de 7 avec ses 1.016.568 chiffres.
Par contre, le même raisonnement avec $(3n+1)/2$ ferait intervenir une grosse puissance de 3/4 ; celui-ci étant plus petit que 1, ses puissances successives tendent vers 0. C’est cela même qui semble empêcher l’existence de trajectoires divergentes pour la transformation de Collatz.
Cycles
Parmi les résultats partiels connus sur le problème $3n+1$, l’un affirme que si, contre toute attente, il existait un cycle autre que le cycle 1,4,2,1 de longueur 3, alors il serait forcément gigantesque. Voici un énoncé plus précis.
Comment prouver une telle affirmation ? Dans une suite à cet article, on le fera en 3 étapes :
- D’abord, en montrant que tout cycle donne lieu à une équation très contraignante sur ses termes.
- Puis en déduisant de cette équation une estimation fine de la proportion des nombres respectifs de pairs et d’impairs dans le cycle.
- Enfin, en invoquant la théorie des approximations rationnelles d’un nombre réel.
Pour être effective, la troisième étape utilise la validité du problème $3n+1$ jusqu’à $5\cdot 10^{18}$ obtenue par Tomás Oliveira e Silva.
Conclusion
D’innombrables problèmes ouverts défient les mathématiques. Mais parmi eux, le plus élémentaire n’est-il pas le problème $3n+1$ ? Ce qui rend celui-ci si convaincant comme candidat à ce titre, c’est
- l’accessibilité de son énoncé à un très jeune âge ;
- sa propriété d’être instantanément expérimentable à la main.
Puisse cette question susciter un débat dans Images des Mathématiques, et contribuer à faire connaître d’autres problèmes ouverts étonnants.
L’auteur remercie Avner Bar-Hen, Etienne Ghys et Bruno Martin pour leurs commentaires, et Carole Gaboriau pour son aide technique.
La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Christophe Boilley, Gilles Damamme, Joël Merker, P.Levallois, struffi, Simon Billouet et Jérôme Buzzi.
Notes
[1] Les mathématiciens sont d’incorrigibles adeptes — par nécessité — de l’économie de notation.
[2] J’ai bien essayé, lors d’un congrès en 1995 au lac Balatonlelle en Hongrie, d’engager une discussion avec lui sur ce problème. Sa réaction à ce sujet est bien connue, comme j’ai pu le vérifier instantanément : « That’s hopeless », « C’est sans espoir ».
[3] Merci à Joël Merker pour ce lien.
[5] Avec la liaison $1 \rightarrow 4$ supprimée, pour des raisons liées au logiciel de dessin automatique de graphes.
[6] Merci à Avner Bar-Hen pour ce lien.
[8] Pour un autre exemple de système dynamique discret dans Images des Mathématiques, voir le récent article Tourner en rond avec une rotation de Sylvie Ruette.
[10] American Mathematical Society, 2010. Entre autres qualités, ce livre met en avant la richesse des liens entre le problème $3n+1$ et d’autres branches des mathématiques, et reproduit plusieurs articles fondateurs sur le sujet. Le lien vers « Book : The Ultimate Challenge : The 3x+1 Problem » dans la page web de Lagarias donne accès à quelques sections du livre, dont un survol de 27 pages en anglais accessible en suivant le lien vers « Preview Material ».
[11] On conjecture que ce sont les seuls.
[12] Notons que si $n$ est impair, alors $5n+1$ est pair, et ira donc sur $(5n+1)/2$ au pas suivant.
[13] C’est elle, l’hypothèse osée mais plausible.
Partager cet article
Pour citer cet article :
Shalom Eliahou — «Le problème 3n+1 : élémentaire mais redoutable (I)» — Images des Mathématiques, CNRS, 2011
Laisser un commentaire
Articles suggérés
Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :
-
le 21 mars 2014[Rediffusion d’un article publié le 21 mars 2014] Pensiez-vous tout savoir sur cette vieille connaissance qu’est la suite de Fibonacci ? Détrompez-vous !lire l'article -
-
Actualités des maths
-
5 mars 2023Maths en scène : Printemps des mathématiques (3-31 mars)
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
Commentaire sur l'article
Trajectoires divergentes
le 13 novembre 2011 à 21:53, par Pierre Colmez
Trajectoires divergentes
le 14 novembre 2011 à 13:06, par électron
Trajectoires divergentes
le 6 avril 2016 à 13:32, par AITYOUSSEF ABDELKARIM
Élémentaire
le 8 janvier 2018 à 21:20, par ayoub dz
Le problème 3n+1 : élémentaire mais redoutable (I)
le 17 novembre 2011 à 08:08, par Marc JAMBON
Le problème 3n+1 : élémentaire mais redoutable (I)
le 17 novembre 2011 à 12:45, par Shalom Eliahou
Le problème 3n+1 : élémentaire mais redoutable (I)
le 20 mai 2012 à 20:53, par Sve@r
Autre définition de la suite
le 20 mai 2016 à 02:19, par PANTAGO
Le problème 3n+1 : élémentaire mais redoutable (I)
le 25 novembre 2014 à 09:58, par CHEHIKIAN Raymond
Le problème 3n+1 : élémentaire mais redoutable (I)
le 25 novembre 2014 à 17:00, par Shalom Eliahou
Le problème 3n+1 : élémentaire mais redoutable (I)
le 19 mai 2015 à 18:45, par madec
Une manière d’aborder le problème ?
le 18 juin 2015 à 19:06, par Olivier Madec
Une manière d’aborder le problème ?
le 26 juin 2015 à 18:01, par Olivier Madec
Une manière d’aborder le problème ?
le 22 juillet 2015 à 19:00, par Olivier Madec
Le problème 3n+1 : Où est le problème ?
le 11 décembre 2015 à 13:58, par Kimyh
Le problème 3n+1 : Où est le problème ?
le 22 juillet 2016 à 18:30, par Olivier Madec
Le problème 3n+1 : élémentaire mais redoutable (I)
le 5 avril 2016 à 20:34, par AITYOUSSEF ABDELKARIM
Le problème 3n+1 : élémentaire mais redoutable (I)
le 18 novembre 2018 à 09:47, par Pierre Cami
Le problème 3n+1 : élémentaire mais redoutable (I)
le 18 novembre 2018 à 15:24, par Pierre Cami
Le problème 3n 1 : élémentaire mais redoutable (I)
le 18 novembre 2018 à 16:41, par Pierre Cami
Le problème 3n 1 : élémentaire mais redoutable (I)
le 22 décembre 2018 à 15:47, par électron
Le problème 3n 1 : élémentaire mais redoutable (I)
le 23 décembre 2018 à 10:03, par Pierre Cami
Le problème 3n 1 : élémentaire mais redoutable (I)
le 20 janvier 2020 à 11:22, par CAMI