Le problème 3n+1 : élémentaire mais redoutable (I)

Piste verte 13 novembre 2011  - Ecrit par  Shalom Eliahou Voir les commentaires (16)

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 :

PNG - 165.6 ko

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 :
    PNG
  • 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.

Théorème. La transformation de Collatz n’admet, sur les entiers positifs, aucun cycle de longueur comprise entre 4 et 17.000.000.000.

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.

Post-scriptum :

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.

Article édité par Étienne Ghys

Notes

[1Les mathématiciens sont d’incorrigibles adeptes — par nécessité — de l’économie de notation.

[2J’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 ».

[3Merci à Joël Merker pour ce lien.

[5Avec la liaison $1 \rightarrow 4$ supprimée, pour des raisons liées au logiciel de dessin automatique de graphes.

[6Merci à Avner Bar-Hen pour ce lien.

[8Pour 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.

[9Suivre le lien vers « 3X+1 Problem » dans sa page web.

[10American 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 ».

[11On conjecture que ce sont les seuls.

[12Notons que si $n$ est impair, alors $5n+1$ est pair, et ira donc sur $(5n+1)/2$ au pas suivant.

[13C’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

Crédits image :

Image à la une - L’auteur remercie Jason Davies, créateur du logo.

Commentaire sur l'article

  • Trajectoires divergentes

    le 13 novembre 2011 à 21:53, par Pierre Colmez

    Il est plus raisonnable de ne regarder que les nombres impairs de la suite, et on peut se demander quelle est la taille de $u_{n+1}$ en fonction de $u_n$. Or pour passer de $u_n$ à $u_{n+1}$ on commence par multiplier par $3$ et ensuite on divise par une puissance de $2$, à savoir $2$ une fois sur deux, $4$ une fois sur quatre, $8$ une fois sur huit, etc. En moyenne, on a $u_{n+1}\sim 3(\frac{1}{2^2}+\frac{1}{4^2}+\frac{1}{8^2}+\cdots)u_n=u_n$. Donc en moyenne la suite de Collatz ne bouge pas alors que celle basée sur $5x+1$ fournit une dilatation moyenne de rapport $5/3$.

    Répondre à ce message
    • Trajectoires divergentes

      le 14 novembre 2011 à 13:06, par électron

      Oui, à un « détail » près : il faut ici raisonner en moyenne géométrique. Pour le problème 3n+1, on arrive à la formule heuristique $(\frac{3}{2})^{\frac{1}{2}} (\frac{3}{4})^{\frac{1}{4}} (\frac{3}{8})^{\frac{1}{8}} \cdots$ ce qui donne, tous calculs faits, un facteur moyen égal à $\frac{3}{4}$ entre deux termes impairs d’une même suite. Il y a donc contraction en moyenne, ou du moins on s’attend à observer un comportement « globalement » décroissant. Nous obtenons de cette manière une estimation effective de la vitesse de contraction, qui semble fonctionner pour « la plupart » des suites. Cet argument a été formulé dans les articles de Crandall (1978), Lagarias (1985), et plus récemment Jean-Paul Delahaye (1998, Pour la Science no 247). Il est possible de simplifier le raisonnement en considérant « l’accélération » $n -> (3n+1)/2$ pour tout $n$ impair ...

      Dans le cas de la variante 5n+1, le même argument conduit à un facteur moyen égal à $\frac{5}{4}$ entre les termes impairs.

      Olivier

      Répondre à ce message
      • Trajectoires divergentes

        le 6 avril à 13:32, par AITYOUSSEF ABDELKARIM

        Que veut dire trajectoire divergente ?

        Répondre à ce message
  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 17 novembre 2011 à 08:08, par Marc JAMBON

    Si on remplace 3n + 1 par 3n -1 on obtient :
    2 ; 1
    3 ; 8 ; 4 ; 2 ; 1
    4 ; 2 ; 1 
    mais
    5 ; 14 ; 7 ; 20 ; 10 ; 5
    là on a un cycle non trivial, le procédé se poursuit sans fin.

    Répondre à ce message
    • Le problème 3n+1 : élémentaire mais redoutable (I)

      le 17 novembre 2011 à 12:45, par Shalom Eliahou

      Effectivement, remplacer 3n+1 par 3n-1 revient à considérer 3n+1 sur les entiers négatifs. On retrouve alors les trajectoires cycliques de -5 et de -17.

      Shalom

      Répondre à ce message
  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 20 mai 2012 à 20:53, par Sve@r

    Bonjour
    Je pense que ce problème ne peut pas se résoudre parce que la formulation « si n est pair » ne possède pas d’opérateur mathématique. En effet, on peut formuler « ajouter » par le signe « + » qui possède ses propriétés (commutativité, associativité, etc) et on peut ensuite le lier aux autres par des factorisations ou des développement pour simplifier ses opérations comme a * (b+c) mais en revanche on n’a pas de symbole ou d’outil pour signifier « si » et donc on ne peut pas simplifier la formulation « si n pair => n/2 sinon 3n+1 »...

    Répondre à ce message
    • Autre définition de la suite

      le 20 mai à 02:19, par PANTAGO

      (Ne sachant pas comment noter ici les indices et les exposants, je note u1 le terme qui suit u).
      La définition de la suite peut s’écrire :
      u1=( 7u + 2)/4 -[ (-1)^u] (5u +2 )/4
      Ca ne résout pas le problème, mais c’est amusant.

      Répondre à ce message
  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 25 novembre 2014 à 09:58, par CHEHIKIAN Raymond

    J’ai pu vérifier - par ordinateur avec un programme que j’ai personnellement réalisé - la conjecture « jusqu’à »
    x.10^1200 (temps de calcul et affichage de l’ordre de 6 minutes). Je puis vous adresser un document de vol d’un nombre
    défini aléatoirement et ayant exactement 1200 chiffres.
    Je précise que j’ai pu vérifier pour un tel nombre et non pas de 4 à ce nombre..

    Répondre à ce message
    • Le problème 3n+1 : élémentaire mais redoutable (I)

      le 25 novembre 2014 à 17:00, par Shalom Eliahou

      Je voudrais préciser qu’avec des gros systèmes de calcul formel comme Sage (gratuit), Mathematica ou Maple par exemple, on peut faire de l’arithmétique exacte sur des nombres entiers arbitrairement grands — la seule limite étant la mémoire disponible. Mais typiquement, avec ces systèmes, on peut faire des calculs exacts rapides sur des nombres à 100000 chiffres par exemple.

      Votre mérite, bien sûr, est d’avoir tout programmé vous-même ! Alors oui, volontiers, envoyez-moi un tel document généré par votre programme.

      Répondre à ce message
  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 19 mai 2015 à 18:45, par madec

    C’est effectivement un très beau problème d’arithmétique.

    Répondre à ce message
  • Une manière d’aborder le problème ?

    le 18 juin 2015 à 19:06, par Olivier Madec

    Voici, peut-être, une manière d’aborder le problème :
    A un nombre entier n on peut définir une trajectoire libre ou naturelle par la transformation de Collatz.
    A un nombre entier m on peut définir une trajectoire contrainte
    à partir de la trajectoire libre d’un autre entier n en essayant de forcer l’entier m à suivre la trajectoire de n
    au lieu de sa trajectoire naturelle.
    Ou encore, de manière plus large, on peut définir une trajectoire contrainte de m en définissant pour cet entier
    une trajectoire guidée par celle libre de n.
    On pourra essayer de définir une trajectoire contrainte ou bien, inversement, essayer de retrouver une définition possible à partir d’exemples.

    L’avantage d’une trajectoire contrainte est qu’elle pourra être définie pour des réels et dépendre de paramètres.

    Comme il a plusieurs façons de définir des trajectoires contraintes pour une même trajectoire libre d’un entier, il est utile de
    les faire apparaître sur une même table.Toutes ces trajectoires apparaissent alors comme des trajectoires
    conjointes ce qui pourrait éventuellement permettre une analyse d’ensemble.

    Voici quelques exemples :
    En première ligne se trouve la trajectoire libre de n
    (Sortie : Console du logiciel R).

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15 65 65 225 225 225 225 687 687 2079 2079 2079 6251 6251 6251 6251 18759 18759 18759 18759 18759
    [3,] 58 175 87 262 131 65 32 97 48 145 72 36 109 54 27 13 40 20 10 5 2
    [4,] 131 452 2 94 -608 2 2 39 -223 -620 2 -179 -500 2 -134 2 20 -90 -95 2 2


    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19.00000 58.00000 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 65.00000 65 225 225 225 225 687 687 2079 2079 2079 6251 6251 6251 6251 18759 18759 18759 18759 18759
    [3,] 10.75833 33.27499 16 49 24 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 131.00000 404.75833 14 59 -93 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1


    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
    [1,] 29.00000 88.0000 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 75.0000 75 75 75 237 237 729 729 729 2201 2201 2201 2201 6609 6609 6609 6609 6609
    [3,] 16.53183 50.5955 25 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 131.00000 410.5318 10 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1


    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
    [1,] 29.00000 88.0000 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 75.0000 75 75 75 237 237 729 729 729 2201 2201 2201 2201 6609 6609 6609 6609 6609
    [3,] 16.53183 50.5955 25 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 531.00000 1610.5318 2 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1


    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19.000000 58.00000 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 125.000000 395.00000 395 1215 1215 1215 1215 3657 3657 10989 10989 10989 32981 32981 32981 32981 98949 98949 98949 98949 98949
    [3,] 10.758330 33.27499 16 49 24 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 3.141593 21.18311 5 32 2 -59 2 13 -41 -113 2 -34 -94 -102 2 2 9 -13 -14 2 1


    Remarquons alors la suite 2, 2, 9, -13, -14, 2, 1.

    Répondre à ce message
    • Une manière d’aborder le problème ?

      le 26 juin 2015 à 18:01, par Olivier Madec

      Je voudrais apporter quelques précisions à la suite
      de mon commentaire.

      Nous avons vu que nous pouvions définir la notion de trajectoire
      contrainte d’un nombre m par rapport à un entier n, et en
      particulier, celle qui consiste à obliger à m à suivre, le plus
      possible, le mouvement libre de n.

      Dans ce cas, la trajectoire contrainte de n par rapport à lui-même
      doit correspondre à sa propre trajectoire libre.

      je donne 2 exemples où la trajectoire contrainte de m par rapport à n rejoint la trajectoire libre de n,
      les deux trajectoires ayant la même longueur.

      2 exemples (Sortie : Console du logiciel R) :

      Avec n=180 et m=216.6779 (lignes 1 et 3).
      Les trajectoires se rejoignent au rang 14 avec 5 comme nombre conjoint.

      Avec n=720 et m=832.6968 (lignes 1 et 3).
      Les trajectoires se rejoignent au rang 15 avec 10 comme nombre conjoint.

      Exemple 1 :

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
      [1,] 180.0000 90 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
      [2,] 125.0000 125 125 421 421 421 421 1281 1281 1281 3857 3857 3857 3857 11577 11577 11577 11577 11577
      [3,] 216.6779 108 54 163 81 40 20 61 30 15 46 23 11 5 16 8 4 2 1
      [4,] 180.0000 5 2 61 2 -3644 -3622 -10845 2 -1349 -4031 2 -1034 -1012 -3030 -2235 2 -179 2

      Exemple 2 :

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
      [1,] 720.0000 360 180 90 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
      [2,] 125.0000 125 125 125 125 421 421 421 421 1281 1281 1281 3857 3857 3857 3857 11577 11577 11577 11577 11577
      [3,] 832.6968 416 208 104 52 157 78 39 19 58 29 14 43 21 10 5 16 8 4 2 1
      [4,] 720.0000 2 -74879 2 -18719 -56104 -56312 -42196 -28118 -84334 -52607 2 21 2 -3779 2 12 -2874 -2877 2 -359

      Pour un entier n donné, il pourrait être intéressant de trouver « son nombre conjoint » (on suppose que
      l’on peut lui associer un réel de manière privilégiée, de sorte que les deux trajectoires se rejoignent comme dans les deux exemples précédents) ...

      Répondre à ce message
      • Une manière d’aborder le problème ?

        le 22 juillet 2015 à 19:00, par Olivier Madec

        Précisons encore... Un entier naturel (supérieur à deux) possède un nombre conjoint qui lui est
        strictement inférieur. Mais ce nombre conjoint possède lui-même un nombre conjoint pourvu
        qu’il soit supérieur à deux. De proche en proche on aboutit soit à 2 soit à 1.
        Autrement dit, il existe une sous-suite décroissante et convergente vers 1 ou 2 dans la trajectoire de Collatz. Ce résultat, si on pouvait le démontrer, suffirait pour pouvoir conclure quant à la conjecture de Collatz.

        Il me semble intéressant de donner ici la table de ces sous-suites pour chaque entier de 3 à 50.
        (Sortie logiciel R).

        [1] 3 1
        [1] 4 1
        [1] 5 1
        [1] 6 1
        [1] 7 2
        [1] 8 1
        [1] 9 4 1
        [1] 10 2
        [1] 11 2
        [1] 12 4 1
        [1] 13 2
        [1] 14 4 1
        [1] 15 4 1
        [1] 16 2
        [1] 17 4 1
        [1] 18 4 1
        [1] 19 4 1
        [1] 20 4 1
        [1] 21 2
        [1] 22 4 1
        [1] 23 4 1
        [1] 24 4 1
        [1] 25 4 1
        [1] 26 4 1
        [1] 27 5 1
        [1] 28 4 1
        [1] 29 4 1
        [1] 30 4 1
        [1] 31 5 1
        [1] 32 2
        [1] 33 5 1
        [1] 34 4 1
        [1] 35 4 1
        [1] 36 13 2
        [1] 37 4 1
        [1] 38 5 1
        [1] 39 5 1
        [1] 40 4 1
        [1] 41 5 1
        [1] 42 2
        [1] 43 13 2
        [1] 44 4 1
        [1] 45 4 1
        [1] 46 4 1
        [1] 47 5 1
        [1] 48 3 1
        [1] 49 13 2
        [1] 50 5 1

        Répondre à ce message
  • Le problème 3n+1 : Où est le problème ?

    le 11 décembre 2015 à 13:58, par Kimyh

    Avant de savoir si l’ont peux échapper à 1, il faut réfléchir à comment arriver à 1.

    Selon la formule, deux possibilités :

    * Diviser le chiffre pair 2
    * Avoir un nombre impair qui multiplié par 3 donne 0 (ce qui est donc exclut)
    La seule solution réside dans le fait de tomber sur le chiffre 2

    Hors, la configuration du calcul nous fait immanquablement tomber sur un nombre pair, qui sera donc divisible par 2. Et même si le résultats est impair, le résultat suivant le sera.
    De ce fait, quel que soit la grandeur du nombre, selon le schéma de ce calcul, il nous ramènera à 2, et donc à 1.

    Je peux également l’expliquer d’une autre façon :

    Je peux multiplier 1 par 2.
    Tout nombre entier qui est multipliable par 2 me ramènera à 1 selon la formule proposée.
    Est-ce qu’il existe un nombre entier que je ne peux pas multiplier par 2 ? Non.
    De ce fait, quel que soit le nombre, et la trajectoire qui en découlera, le résultat final sera 1

    Quelqu’un peut-il prouver que je me trompe ?

    Kimyh

    Répondre à ce message
    • Le problème 3n+1 : Où est le problème ?

      le 22 juillet à 18:30, par Olivier Madec

      Il me semble que si votre raisonnement était juste il devrait pouvoir également s’appliquer aux entiers négatifs.
      Or pour -5 cela ne fonctionne pas à cause du cycle -5 -14 -7 -20 -10 (ce qui exclut qu’on puisse « arriver » à 1 pour -5).

      Répondre à ce message
  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 5 avril à 20:34, par AITYOUSSEF ABDELKARIM

    Est-il vrai qu’il n’y a aucune trajectoire divergente ?

    A ma connaissance toute trajectoire est limitée et est divergente : ne possède pas de limite finie ou infinie.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM