Un regard sur la conjecture de Collatz

[Ben314]

La précision, il la donne en dessous :
Pour montrer que, partant de n'importe quel entier N >= 2 on finit par tomber sur 1, il suffit bien sûr de montrer que, partant de N, on finit par tomber sur un entier <N (c'est une application immédiate du principe de récurrence)

Par exemple, partant de 41, on obtient 41 -> 124 -> 62 -> 31 et c'est fini en 3 coups vu qu'on a obtenu un entier <41 dont on "sait" déjà qu'il finit par donner 1 vu qu'on raisonne par récurrence.
Et c'est bien sûr la même chose pour tout les N=4k+1 vu que N=4k+1 -> 12k+4 -> 6k+2 -> 3k+1 qui est <N (si k est supérieur ou égal à 2).

Donc effectivement, partant d'un entier pair (>=2), comme le suivant est directement N/2 <N, c'est fini.
Et de façon plus générale, si sait à quoi N est congru modulo 2^k alors on sait quelle vont être les k premières opérations avec ce N là comme "germe" et on peut facilement regarder de proche en proche (i.e. en augmentant k de 1 en 1) quels sont les seules congruences modulo 2^k qui ne donnent aucun nombre <N parmi les k étapes suivantes.

Évidement et très clairement, ce nombre "d’exceptions" est de plus en plus faible en proportion du nombre de résidus modulo 2^k (tout simplement du fait qu'à chaque fois on ne fait qu'éliminer des éléments), mais par contre en terme de quantité, il est de plus en plus grand (et on peut même en avoir une estimation asymptotique en regardant combien il faut de division par 2 pour compenser les multiplication par 3). Bref, la méthode donne l'impression de donner des résultat tout en disant parfaitement bien quelles sont ces limites, à savoir qu'on n'obtiendra jamais de preuves par cette voie là. Sans parler du fait que, si on montre uniquement que certains "germes" N (et pas tous) finissent par donner un nombre <N, ça fout toute la récurrence à l'eau et ça ne constitue donc même pas une preuve que ces "germes" là finissent par tomber sur 1.

[Ben314]

ERREUR...

[aviateur]

D'accord @pseuda j'ai compris. Excuse-moi.

[Pseuda]

C'est surement un problème passionnant qui pose beaucoup plus de questions que de réponses.

On peut certainement trouver tout un tas de propriétés concernant cette suite, je n'en doute pas. Pour moi, l'affaire est faite : la plupart des nombres reviennent à 1 de par leurs propriétés arithmétiques.

Par exemple, les 4n+1 -> 12n+4 -> 6n+2 -> 3n+1 (< 4n+1), c'est fini. Je n'ai même pas vérifié les autres.

Et une petite minorité donnent des résultats erratiques, pour une raison bien mystérieuse, mais finissent, du fait de leur resserrement, par tomber sur une puissance de 2, pour redescendre à 1.

Mais évidemment cela n'explique pas le manque de boucle. Pour les 3n-1, il semble que la boucle ne se produit que sur 1, 7 et 61, soit des nombres petits (j'ai dû aller jusqu'à 10000).

[Ben314]

Que cette conjecture soit vraie ou fausse, ce qui est remarquable c'est déjà de trouver cela.

Sinon, à mon sens en tout cas, ce type de conjecture, c'est "zéro remarquable" vu qu'en fait c'est exactement ce qu'on obtiendrait comme type de résultat si, au lieu d'être déterminées par la parité de Un, le choix de l'opération à mener (entre faire N/2 et (3*N+1)/2) était tiré au hasard.
Donc tout ce que (pré)dit la conjecture, c'est que "globalement" (i.e. sur un vaste nombre d'entier), les effets qu'ont les X->X/2 et les X->(3X+1)/2 sont les mêmes que si ces deux opérations étaient tirées au pif (avec 50% de chance pour chacune d'elle).
Bref, c'est à mon avis un peu comme le fait que Pi soit un nombre univers : ça semble on ne peut plus plausible vu qu'au fond, c'est "la normalité aléatoire".

P.S. (@aviateur) : Tu peut tout à fait calculer (vu que c'est élémentaire) le nombre moyen d'opérations qu'il faut partant d'un réel de [1,x]pour tomber sur un réel <=1 en faisant au random (50/50) soit des division par 2, soit des multiplications par 3/2 ( en négligeant le +1 du X-> (3X+1)/2 ). Tu vérifiera ainsi qu'on tombe bien sur la conjecture en question.

[Pseuda]

Ce qui est bizarre, c'est que la petite minorité qui fait des résultats très erratiques, fait vraiment n'importe quoi. Je veux dire par là, qu'il n'y a plus aucune logique dans le nombre de pas pour redescendre en-dessous de leur point de départ, comme si toutes leurs propriétés arithmétiques (congruences modulo 2^k notamment) avaient disparues. Très mystérieux.

[Ben314]

Je sais pas jusqu'où tu as regardé, mais la "logique", elle perdure parfaitement. Et cette logique c'est quoi ?
Ben c'est que en général (et on peut calculer précisément avec quelle réquence quie st du ln(3)/ln(2) ou un truc du même style) en augmentant k de 1 dans la congruence modulo 2^k, ben ça double évidement le nombre de résidus "non encore éliminés" que l'on a, mais ensuite, ce nombre est de nouveau divisé par 2 vu que pour la moitié de ces résidus, la dernière opération est une division par 2 qui les fait passer en dessous de N. Sauf que ça déconne régulièrement du fait que, vu le nombre de multiplication par 3 où on en est, ben une seule division par 2 de plus ne suffit pas à faire passer en dessous de N et là, ben y'a rien qui s'élimine et effectivement on a 2 fois plus de résidus modulo 2^(k+1) que ce qu'on en avait modulo 2^k.

Tu est allé jusqu'à quelle valeur de k pour voir combien il y a de résidus "qui résistent" ?
A mon avis, si tu veut bien te rendre compte du bidule, il faut aller au moins jusqu'à 50 (donc 2^50 ce qui est totalement immédiat pour un ordinateur).

[Pseuda]

Je ne suis pas sûre de bien comprendre. A chaque fois qu'on augmente la puissance de 2, de 1 à voire 3 (par exemple quand on passe de 32 à 128 ou 256), on élimine de nouveaux candidats (une opération mécanique qui tient de leur arithmétique les fait redescendre), donc le nombre de résidus diminue, cela ne peut pas l'augmenter ?

[aviateur]

Oui @ben tu as raison de faire remarquer que la conjecture traduit grosso modo le fait qu'il y a approximativement autant de 3x+1 que de x/2. Mais en quoi c'est zéro remarquable, sinon que de dire que c'est évident (ou assez logique) d'y penser?

[Ben314]

Je ne suis pas sûre de bien comprendre. A chaque fois qu'on augmente la puissance de 2, de 1 à voire 3 (par exemple quand on passe de 32 à 128 ou 256), on élimine de nouveaux candidats (une opération mécanique qui tient de leur arithmétique les fait redescendre), donc le nombre de résidus diminue, cela ne peut pas l'augmenter ?

Oui, on élimine des candidats, mais quand tu passe des résidus modulo 2^k à ceux modulo 2^(k+1), ça te fait mécaniquement deux fois plus de résidus : UNE congruence modulo 2^k, ça correspond à DEUX congruences modulo 2^(k+1).
Si on reprend plus en détail la prose de pseuda ça dessus on a :
- Modulo 2, il y a deux résidus possibles qui sont 0 ou 1, mais 0 est éliminé vu qu'il conduit immédiatement à un nombre strictement plus petit que le N de départ.
- Modulo 2, il reste donc un seul résidu, à savoir 1, mais cet unique résidu modulo 2 correspond à 2 résidus modulo 4, à savoir 1 et 3. Sauf que 1 est éliminé vu que N=4k+1 -> 12k+4 -> 6k+2->3k+1 < N
- Il reste donc un seul résidu modulo 4, à savoir 3, mais cet unique résidu modulo 4 correspond à 2 résidus modulo 8, à savoir 3 et 7. Et là, aucun des deux n'est éliminé vu que N=8k+3 -> 24k+10 -> 12k+5 -> 36k+16 -> 18k+8 -> 9k+4 -> "on ne sait pas" (avec rien de <N dans la liste) et N=8k+7 -> 24k+22 -> 12k+11 -> 36k+34 -> 18k+17 -> 54k+52 -> 27k+26 -> "on ne sait pas" (avec rien de <N dans la liste).
- Il reste donc deux résidus modulo 8, à savoir 3 et 7 c'est à dire quatre résidus modulo 16, à savoir 3,7,11 et 15 . . .
- etc etc etc...

Oui @ben tu as raison de faire remarquer que la conjecture traduit grosso modo le fait qu'il y a approximativement autant de 3x+1 que de x/2. Mais en quoi c'est zéro remarquable, sinon que de dire que c'est évident (ou assez logique) d'y penser?

Ben je sais pas : ça signifie quoi pour toi le mot "remarquable" ?
Parce que pour moi, un résultat de math "remarquable", c'est :
- Soit un truc qui peut éventuellement être "intuitivement évident" mais très difficile à démontrer et qu'on a quand même réussi à démontrer (style le théorème de Jordan pour les courbes planes). Sauf que là, on a rien démontré du tout.
- Soit un truc plutôt "complètement contre intuitif" qu'on conjecture ou qu'on a éventuellement démontré y compris avec une preuve simple (style le paradoxe de Banach-Tarski dont la preuve n'est pas franchement compliquée). Sauf que là, c'est tout le contraire vu que le résultat et celui qui "colle" le mieux avec l'intuition (intuition disant que c'est bien le bordel et donc que ça va sans doute se comporter comme un truc aléatoire)

Mais bon, de toute façon, c'est juste un problème de vocabulaire : pour moi, cette conjecture elle est "totalement naturelle" (exactement comme celle disant par exemple que Pi est un nombre univers) et par conséquent pas "remarquable" du tout.

[nodgim]

@Ben: j'avai fait ce calcul à la main jusqu'à 2^9 (512) et il me restait, de mémoire, 65 nombres, ce qui donnait un taux d'environ 0,13. Comme tu disais, si le taux baisse infiniment, le nombre de nombres résiduels augmente en absolu.

Sinon, on peut se prêter à ce petit problème sympa :
Soit (a1,a2,a3,.....an) un nuplet, ai représentant la puissance de 2 après la multiplication par 3. Pour un tel nuplet, il existe toujours un couple d'entiers (a,b) tel que si "a" est le nombre initial et "b" un paramètre qui remplace " 1 " dans "3n + 1 " on établit une boucle a----> a après n itérations.

[Pseuda]

Oui, on élimine des candidats, mais quand tu passe des résidus modulo 2^k à ceux modulo 2^(k+1), ça te fait mécaniquement deux fois plus de résidus : UNE congruence modulo 2^k, ça correspond à DEUX congruences modulo 2^(k+1).
Si on reprend plus en détail la prose de pseuda ça dessus on a :
- Modulo 2, il y a deux résidus possibles qui sont 0 ou 1, mais 0 est éliminé vu qu'il conduit immédiatement à un nombre strictement plus petit que le N de départ.
- Modulo 2, il reste donc un seul résidu, à savoir 1, mais cet unique résidu modulo 2 correspond à 2 résidus modulo 4, à savoir 1 et 3. Sauf que 1 est éliminé vu que N=4k+1 -> 12k+4 -> 6k+2->3k+1 < N
- Il reste donc un seul résidu modulo 4, à savoir 3, mais cet unique résidu modulo 4 correspond à 2 résidus modulo 8, à savoir 3 et 7. Et là, aucun des deux n'est éliminé vu que N=8k+3 -> 24k+10 -> 12k+5 -> 36k+16 -> 18k+8 -> 9k+4 -> "on ne sait pas" (avec rien de <N dans la liste) et N=8k+7 -> 24k+22 -> 12k+11 -> 36k+34 -> 18k+17 -> 54k+52 -> 27k+26 -> "on ne sait pas" (avec rien de <N dans la liste).
- Il reste donc deux résidus modulo 8, à savoir 3 et 7 c'est à dire quatre résidus modulo 16, à savoir 3,7,11 et 15 . . .
- etc etc etc...

Bonjour,

Ok ! (c'est le terme de "résidu" que je ne voyais pas, ne sachant pas s'il s'agissait des classes de congruence ou des nombres eux-mêmes). Quand on augmente la puissance des congruences (de 2^k à 2^(k+1)), il y a des résidus qui s'éliminent, mais apparemment moins de la moitié à chaque fois, donc il en reste toujours.

Par exemple, en partant de k=1, cela élimine la moitié (les pairs). Quand on passe à 2^2, il en reste le quart. De 2^2 à 2^3, cela n'en élimine aucun. Quand on passe de 2^3 à 2^4, cela élimine les 16n+3, soit seulement le quart du reste. Quand on passe de 2^4 à 2^5, il ne reste que 1/8 de la population. De 2^5 à 2^6, aucun n'est éliminé. Etc... Donc il en reste toujours (encore que c'est à voir : si le nombre de résidus tend vers 0 au fur et à mesure qu'on les envisage, sachant que la population reste la même...). C'est cette irrégularité que je trouve surprenante.

Je me suis livrée à une petite étude sur les 2^k-1. Ils font du impair - pair jusqu'à tomber sur (3^(2q)-1)/8 si k=2q, et (3^(2(q+1)-1)/8 si k=2q+1, mais cela reste supérieur à 2^k-1. Pour k=2^q, on a 3^(2^q) congru à 1 modulo 2^(q+2), mais qui ne permet toujours pas de continuer.

Bref, tout cela ne mène à rien. Mais j'ai compris qu'il faut des moyens beaucoup plus puissants et autres, pour arriver à un résultat.

[Pseuda]

Donc effectivement, partant d'un entier pair (>=2), comme le suivant est directement N/2 <N, c'est fini.
Et de façon plus générale, si sait à quoi N est congru modulo 2^k alors on sait quelle vont être les k premières opérations avec ce N là comme "germe" et on peut facilement regarder de proche en proche (i.e. en augmentant k de 1 en 1) quels sont les seules congruences modulo 2^k qui ne donnent aucun nombre <N parmi les k étapes suivantes.

Évidement et très clairement, ce nombre "d’exceptions" est de plus en plus faible en proportion du nombre de résidus modulo 2^k (tout simplement du fait qu'à chaque fois on ne fait qu'éliminer des éléments), mais par contre en terme de quantité, il est de plus en plus grand (et on peut même en avoir une estimation asymptotique en regardant combien il faut de division par 2 pour compenser les multiplication par 3).

Bonsoir,

Ah je crois que cela répond à mon interrogation concernant les irrégularités constatées sur les résidus modulo 2^k. Merci ! Ces résidus deviennent imprévisibles, sauf à aller y regarder, du fait de la multiplication par 3 +1 qui déforme leur comportement face aux 2^k. Même si le nombre de résidus ne fait que baisser en terme de population résiduelle non enlevée, il en reste toujours autant en nombre, voire augmente. Je comprends mieux, enfin je crois, pourquoi cette conjecture n'a pas été démontrée. Elle semble donc l'être difficilement par des arguments arithmétiques, les arguments probabilistes sont rejetés (vu sur le forum), il ne reste plus grand' chose d'autre...

Sinon, en nombres, j'ai été jusqu'à 150000, soit 2^17, mais je n'ai regardé les congruences que jusqu'à 2^8, c'était déjà largement suffisant pour se faire une idée.

[Pseuda]

Bonjour,

Finalement, ce que je trouve le plus surprenant dans cette conjecture (si elle est vraie), ce n'est pas que la suite revient toujours à 1, mais qu'il n'y ait pas de boucle autre que la boucle triviale.

Je m'explique. Quand on est sur un nombre impair x, il est multiplié par 3 +1, soit 3x+1, cela en fait un nombre pair qui est divisé par 2, voire par 4, 8, etc... Un petit calcul montre que ce nombre 3x+1 va être divisé par 3 en moyenne (compte tenu des probabilités), i.e. revenir à x+1/3. Sinon, dans tous les cas, il est divisé par 2, et a une chance sur 2 d'être divisé par 4. Bref, avec les pairs qui eux sont divisés par 2, un nombre a toutes les chances de passer en-dessous de lui-même au bout d'un moment (ou plutôt la probabilité de rester supérieur est presque nulle, à vérifier).

Ceci est intuitif et ne constitue en rien une démonstration. D'ailleurs, plusieurs démonstrations rigoureuses ont été faites qui donnent ce résultat. Donc le surprenant, c'est qu'il n'y ait pas de boucle.

Sa suite "jumelle" : 3n-1 si impair, n/2 si pair, a d'autres boucles que la boucle triviale 1-2-4 (depuis 7 et 61 au moins). Du coup, pourquoi la suite de Collatz n'aurait pas d'autres boucles ? J'y vois plusieurs raisons, et je ne sais pas si une réponse a déjà été apportée à cette question :

- il ne s'en produit pas pour les petits nombres (pure coïncidence), et pour les grands nombres, cela devient de moins en possible : il s'agirait de calculer la probabilité pour un nombre (assez grand) de repasser par lui-même ; je ne sais pas si cela a été fait, mais je dirai que cette probabilité est décroissante avec le nombre

- cela tient à la suite 3n+1 elle-même.

Vos avis ?

[nodgim]

Oui, Pseuda, c'est un peu ça, plus on monte dans les nombres moins on a de chance de trouver une boucle dans la suite.

Tu peux élargir le débat avec les suites de cette forme, qui englobent notre suite (3n+1)/2 :
u(n+1) = u(n) / k si u(n) divisible par k, sinon [u(n)*(k+1)/k] + 1.
k étant un entier naturel donné > 1.
Elles donnent des suites de nombres bien plus faciles à deviner pour k > 2, et elles sont faciles à programmer.
Certaines d'entre elles n'ont qu'une seule boucle, d'autres 2 ou 3.

Attention, ce problème est addictif !

[Pseuda]

Oui, on peut s'intéresser à d'autres suites similaires et étudier leur comportement, afin de comprendre pourquoi la suite 3n+1 est particulière.

En effet ce problème est addictif, mais je vais très vite m'en sortir, car je suis à peu près persuadée maintenant qu'on n'arrivera pas à démontrer cette conjecture.

En effet, si les nombres reviennent à 1, c'est en raison de leurs propriétés arithmétiques (congruences modulo 2^k réagissant aux multiplications par 3 +1 et divisions par 2), mais ces mêmes propriétés arithmétiques (congruences modulo 2^k successifs qui dictent leur comportement) nous empêchent (ou sont insuffisantes) pour conclure que tous les nombres vont revenir à 1 (j'en ai été persuadée avec mon tableau Excel, puis les remarques de @Ben314, et le comportement erratique de la suite en fonction du 1er terme, comme une fuite en avant ou un éparpillement au fur et à mesure qu'on les envisage). Donc si elles reviennent à 1, cela relève des probabilités, pas d'un argument arithmétique.

Et sa seule chance de faire une boucle autre que la suite triviale est pour les petits nombres, et cette chance va en diminuant avec les grands nombres, mais la probabilité n'est pas nulle. Donc si elle ne le fait pas, ce n'est que pure coïncidence (ce n'est pas en raison d'un argument arithmétique).

Donc en fait, mathématiquement parlant, cette conjecture est fausse (en raison de l'argument arithmétique), sauf à raisonner avec des arguments probabilistes (mais qui ne sont pas recevables). Mais à l'inverse malheureusement, on n'a pas encore trouvé un contre-exemple de boucle (une probabilité qui tend vers 0 n'est pas nulle, donc ce n'est pas impossible), ou de germe qui donnerait une suite qui tend vers l'infini, et les arguments probabilistes disent que c'est impossible mais ne sont pas recevables, donc au final, on est dans l'impasse. En résumé, les suites reviennent à 1 pour des raisons probabilistes mais qu'on n'a pas le droit d'évoquer.

Donc en fait, il faudrait, soit trouver un contre-exemple d'un nombre qui fait une boucle, ou d'un nombre qui part à l'infini (mais cela parait improbable car on a testé tous les nombres jusqu'à 10^20 et on ne voit pas pourquoi on en trouverait un parmi les nombres supérieurs), ou démontrer rigoureusement qu'il est impossible de démontrer la conjecture de Collatz (avec les arguments plus hauts).

Finalement, ce problème tient plus du domaine algorithmique que du domaine mathématique. Si cette conjecture est démontrée, ce serait avec des arguments algorithmiques. Donc pour moi, c'est une pure perte de temps.