Collatz et les puissances de 2

[G.Renault]

Bonjour,

L'article est amusant à lire mais certaines définitions sont un peu obscures je trouve (notamment p, ce qui rend la compréhension globale difficile).

Une petite remarque sur le titre : le mot éponyme n'est pas adapté car ce n'est pas l'algorithme qui a donné son nom à Collatz mais bien le contraire.

Cette expression étant ingérable je l’ai convertie en une forme équivalente mais beaucoup plus simple. Et après avoir laborieusement remplacé les divers symboles par des valeurs numériques, en partant de plusieurs valeurs de n0 dont la suite impaire comptait 6 termes, je me suis aperçu qu’elle était toujours égale à 1
[...]
Ça ne pouvait décidément pas être le fruit du hasard. Avec n0=29, par exemple, j’obtenais ceci :
[...]

Je pense que le souci réel posé par ce problème se situe justement dans ce paragraphe.

Tu ne peux pas prendre le problème à l'envers en disant :
- je prends des suites de Collatz dont la suite impaire compte 6 termes ;
- incroyable, dans ce cas là, le 5ème 3nk+1 de la suite est divisible par une puissance de 2 qui aboutit à 1.
Il est évident dans ce cas que ton algo des impairs aboutira à 1 puisque c'est ce que t'a dit la suite de Collatz a priori.

Je crois que la question : "est-ce le fruit du hasard ?" revient à savoir si le fait que la suite de Collatz aboutisse à une puissance de 2 est un hasard ou non. C'est le coeur du problème, ce qui rend fou plein de personnes devant leur petit bout de papier...

En tout cas, courage dans tes recherches.

[syrac]

Une petite remarque sur le titre : le mot éponyme n'est pas adapté car ce n'est pas l'algorithme qui a donné son nom à Collatz mais bien le contraire.

Je viens justement de changer ce titre. Le document s'appelle maintenant "Vers la compréhension du mécanisme en oeuvre dans les suites de Collatz".

Tu ne peux pas prendre le problème à l'envers en disant :
1 - je prends des suites de Collatz dont la suite impaire compte 6 termes ;
2 - incroyable, dans ce cas là, le 5ème 3nk+1 de la suite est divisible par une puissance de 2 qui aboutit à 1.
Il est évident dans ce cas que ton algo des impairs aboutira à 1 puisque c'est ce que t'a dit la suite de Collatz a priori.

1 - Je pense que tu n'as pas compris ce passage. Si j'ai pris pour exemples des valeurs de n0 telles que leur suite impaire comporte 6 termes, c'est parce que j'étudiais l'expression symbolique de n5. Je n'avais pas envie d'avoir à construire l'expression du dernier terme de la suite de n0 pris aléatoirement, il était plus pratique de me concentrer sur des suites de 6 termes.

2 - Non, cette remarque vaut pour l'avant-dernier terme d'une suite impaire, qu'il ne faut pas confondre avec l'expression symbolique du dernier terme.

Je crois que la question : "est-ce le fruit du hasard ?" revient à savoir si le fait que la suite de Collatz aboutisse à une puissance de 2 est un hasard ou non. C'est le coeur du problème, ce qui rend fou plein de personnes devant leur petit bout de papier...

Tu sors toi aussi ma phrase de son contexte. J'ai écris "Ça ne pouvait décidément pas être le fruit du hasard", en parlant du fait que l'expression du dernier terme était toujours égale à 1 lorsque je remplaçais les valeurs symboliques par des valeurs numériques.

Et merci pour tes encouragements ! :we:

[syrac]

Je pense qu'il existe une confusion entre suite impaire et expression symbolique d'une suite impaire. La suite impaire correspond à ceci, avec l'exemple de 29 :

n0 = 29
n1 = 11
n2 = 17
n3 = 13
n4 = 5
n5 = 1

La suite symbolique est celle-ci :



Dans la suite impaire, n5 = 1 est issu du fait que 3*n4+1 est une puissance de 2, ce qui fait que par divisions successives par 2 on abouti à 1 à l'étape suivante, la dernière. Dans l'exemple ci-dessus, n4 = 5 et 3*5+1 = 16. Mais rien n'a jamais permis d'expliquer pourquoi ceci se produisait, c'est-à-dire pourquoi 3*l'avant-dernier terme+1 était une puissance de 2.

Dans la suite symbolique, le dernier terme est égal à 1 pour une raison intrinsèque : ce sont les valeurs des diviseurs successifs qui font que la somme (numérateur) est égale au produit (dénominateur). Cette valeur de 1 n'est aucunement la conséquence du terme précédent.

[G.Renault]

Dans la suite symbolique, le dernier terme est égal à 1 pour une raison intrinsèque : ce sont les valeurs des diviseurs successifs qui font que la somme (numérateur) est égale au produit (dénominateur). Cette valeur de 1 n'est aucunement la conséquence du terme précédent.

Bien sûr que si, le raisonnement que tu fais avec la suite impaire est tout à fait valable pour ta suite symbolique.
D'ailleurs ta nuance me semble bien tirée par les cheveux puisque ta suite impaire correspond simplement aux résultats de tes expressions symboliques pour un n0 particulier choisi au départ.
À partir de là, soit ton est une puissance de 2 (ou si tu préfères ton mais c'est exactement la même chose) et dans ce cas l'algo aboutit à 1, soit ce n'est pas le cas et l'algo continue.

Donc dire que « par hasard » tous tes diviseurs/sommes/produits aux numérateurs et dénominateurs donnent 1 ou que « par hasard » ton avant dernier terme impair est une puissance de 2, c'est exactement la même chose. Tout ça relève du même par hasard et n'est pas explicable/expliqué comme tu l'as précisé dans ton post précédent.
Ce phénomène n'est pas davantage lié aux qu'aux termes de ta suite impaire ou de ta suite de Collatz.
Ce phénomène se produit comme ça, d'un coup, sans crier gare et sans explication ou prévision possible.

D'ailleurs, tu ne peux absolument pas prouver qu'un terme de ta suite symbolique vaut 1 puisque cela dépend justement du n0 choisi. Ce n'est pas du tout un phénomène structurel à ta suite, qui dépendrait de la séquence des ou des puissances de 3 au numérateur par exemple puisque parfois ce quotient vaut 1 (précisément quand le est l'avant dernier terme d'une suite impaire de Collatz et ça on ne sait pas le prédire à l'avance) et le reste du temps il n'a rien à voir avec 1...

Et puis tu peux toujours essayer de trouver un argument sur les ou les impairs pour prévoir que la suite va aboutir à 1 à un moment donné mais tu ne peux pas dire que d'un coup, puisque tu écris une formule explicite qui ne contient pas directement les de ta suite, alors le fait qu'un terme vaille 1 ne dépend pas du terme précédent.

C'est un peu comme si tu considérais une suite définie par , que tu calculais explicitement et que tu disais que d'un coup n'avait plus rien à voir avec .

[nodjim]

C'est pas très probant, Syrac, car tu pars d'un a-priori fatal en logique, à savoir qu'il existe un dernier n, mais c'est justement la recherche de l'exactitude de cette conjecture qui est en jeu. Par ailleurs, il est impossible, tout au moins avec ta démarche, de prévoir à l'avance les valeurs de d1, d2,..dn.

Ah, si tu pouvais prouver qu'il existe une suite utilisant l'inverse de l'algo et qui, en partant de 1, mène à tous les entiers, tu gagnerais le gros lot.....

[syrac]

Bien sûr que si, le raisonnement que tu fais avec la suite impaire est tout à fait valable pour ta suite symbolique.

Il y a dans tout ceci une chose tellement peu évidente qu'il me faut l'expliciter. Je te propose d'ouvrir mon papier à la page 3, sur laquelle figure la suite de cinq tableaux expliquant pas à pas le fonctionnement de l'algorithme. L'information la plus importante dans ces tableaux est la colonne de droite, somme.

Tu constates que ces sommes valent successivement 88, 272, 832, 2560 et 8192. Si maintenant tu prends la suite d'expressions et que tu calcules leur numérateur, en prenant n0 = 29, tu tomberas sur les mêmes chiffres. Autrement dit, l'algorithme ne calcule pas l'expression entière mais son numérateur uniquement.

Pourquoi n'est-il pas nécessaire de calculer l'expression entière ? Parce que l'algorithme se fonde sur la certitude qu'à un moment donné cette somme deviendra une puissance de 2. La dernière ligne de la boucle while calcule la plus grande puissance de 2 divisant somme, par la fonction pgp2(somme), puis débute l'itération suivante en vérifiant que somme est toujours différente de div. Si tu analyses bien ce processus tu constates que le dénominateur des expressions successives n'a aucune importance. Ce qui importe est que la somme finisse par prendre pour valeur une puissance de 2, auquel cas div deviendra égale à somme pour l'unique raison que la plus grande puissance de 2 divisant une puissance de 2 n'est rien d'autre qu'elle-même. Que le produit au dénominateur de la dernière expression soit une puissance de 2 égale à somme est sans signification puisqu'on ne l'a même pas calculé.

Si dans une suite impaire le lien de cause à effet est évident entre l'avant-dernier et le dernier terme, dans la suite de numérateurs il n'existe pas. L'algorithme n'opérant pas de la même manière que la suite impaire, tu ne peux pas les comparer et prétendre qu'ils reviennent à la même chose.

@nodjim

Ah, si tu pouvais prouver qu'il existe une suite utilisant l'inverse de l'algo et qui, en partant de 1, mène à tous les entiers, tu gagnerais le gros lot...

Ce serait au contraire la pire des erreurs ! Partir de 1 signifierait que je fonde mon raisonnement sur un a priori, celui que toute suite se termine par 1.

[nodjim]

"Parce que l'algorithme se fonde sur la certitude qu'à un moment donné cette somme deviendra une puissance de 2"

Là aussi c'est à-priori !

[nodjim]

Ce serait au contraire la pire des erreurs ! Partir de 1 signifierait que je fonde mon raisonnement sur un a priori, celui que toute suite se termine par 1.

Non si tu prouves qu'on peut accéder à n'importe quel nombre (non multiple de 3). Rassure toi, c'est absolument impossible de remonter une suite en visant un nombre.

[syrac]

@G.Renault

Je me suis planté dans mon dernier post. J'ai dit que le dénominateur des expressions successives n'était pas calculé, ce qui est faux. Les deux dernières lignes de la boucle while sont celles-ci :

somme = Total[rangee*listeP3];
div = pgp2[somme] <-- plus grande puissance de 2 qui divise somme

En fait, div prend successivement pour valeur les produits d1, puis d1*d2, puis d1*d2*d3, etc., conformément aux expressions. Seulement, contrairement à ce qui se passe dans le calcul d'une suite impaire, la division somme/div n'est pas effectuée, autrement dit on ne calcule pas la valeur de chaque expression. Si on le faisait on se retrouverait avec les mêmes valeurs que dans une suite impaire, ce qui correspond à ce que tu disais précédemment : "... ta suite impaire correspond simplement aux résultats de tes expressions symboliques pour un n0 particulier choisi au départ". Oui, sauf qu'on ne conserve pas ces résultats.

Ce qui se passe en réalité est que la valeur en cours de div est à chaque itération utilisée pour construire le numérateur de l'expression suivante. Si bien qu'au lieu de se retrouver avec une suite impaire on se retrouve avec une suite de sommes (ou suite de numérateurs) :

Suite impaire : 29, 11, 17, 13, 5, 1
Suite de sommes : 88, 272, 832, 2560, 8192

Dans une suite impaire, lorsque la valeur finale 1 apparaît on sait seulement qu'elle est le résultat du terme qui la précède, point barre. Dans une suite de sommes on sait que la valeur finale 1 est le résultat du fait que le dernier terme est une puissance de 2. La différence est énorme, parce que maintenant on sait d'où elle vient !

[syrac]

"Parce que l'algorithme se fonde sur la certitude qu'à un moment donné cette somme deviendra une puissance de 2"

Là aussi c'est à-priori !

Non, c'est une hypothèse. Le mot certitude était mal choisi. Je viens de faire le test dont je parle plus haut pour tous les entiers impairs compris entre 3 et 99999 (cent mille moins 1). Hypothèse confirmée ! :ptdr:

[nodjim]

Et pour les autres impairs, t'es sûr que ça marche ?

[syrac]

Et pour les autres impairs, t'es sûr que ça marche ?

J'en forme l'hypothèse ! :lol3:

Si ça marche pour les 50000 premiers entiers impairs il n'y a aucune raison pour que ça ne marche pas pour les autres. Je ne vois pas ce qui pourrait amener les nombres à se comporter différemment lorsqu'ils deviennent de plus en plus grands. Leurs propriétés restent les mêmes, ils ne se transforment pas en extraterrestres.

Si on part de 1 et qu'on l'incrémente pendant un an à l'aide d'un ordinateur puissant, il deviendra un nombre gigantesque. Peux-tu m'expliquer à partir de quel moment le fait d'ajouter 1 au nombre en cours va soudainement modifier ses propriétés ?

[Sylviel]

Si ça marche pour les 50000 premiers entiers impairs il n'y a aucune raison pour que ça ne marche pas pour les autres. Je ne vois pas ce qui pourrait amener les nombres à se comporter différemment lorsqu'ils deviennent de plus en plus grands.

C'est que tu n'as pas compris grand chose au principe des maths... Ni à ma parabole du canard.

De la même manière je pourrais affirmer que tous les entiers s'écrivent en base 10 avec moins de 10 chiffres !
Je l'ai testé en une poignée de secondes jusque 999'999'999 !

On peut aussi le formuler autrement :
moi je pense que la suite démarrant par [A(20,20)/2]+1 (les crochets étant pour "partie entière, et A pour la fonction d'ackermann) ne finira pas par 1.

Tiens, pour t'aider à comprendre : personne ne prétends avoir démontré que tous les nombres parfaits soient pairs. En revanche on a pu montré que tous les nombres impairs inférieurs à 10^{1500} ne sont pas parfaits.
http://www.ams.org/journals/mcom/2012-81-279/S0025-5718-2012-02563-4/

[nodjim]

Syrac a compris que son article n'est pas une preuve, mais il le défend comme s'il en était une. Curieux....

[syrac]

Syrac a compris que son article n'est pas une preuve, mais il le défend comme s'il en était une. Curieux....

J'ai commencé l'article en question en disant que je ne cherchais pas à faire une démonstration mais à présenter un processus, en l'occurrence celui mis en oeuvre par l'algorithme.

Ne pas chercher à démontrer = ne pas prétendre prouver.

@Sylviel

En pensée toutes les expériences sont possibles. Et vu qu'il n'y a aucune possibilité de vérification lorsqu'il s'agit de très grands nombres, on peut tout envisager, tout imaginer et tout supposer.

[Sylviel]

Soit, mais dans ce cas là ne fais pas des affirmations du type "j'ai essayé sur 50 000 nombres donc c'est sûrement vrai pour tous".

[syrac]

Soit, mais dans ce cas là ne fais pas des affirmations du type "j'ai essayé sur 50 000 nombres donc c'est sûrement vrai pour tous".

Que se passerait-il si j'en doutais ? Je n'aurais plus qu'à cesser mes recherches pour me mettre au jardinage. Voilà tout ce que le doute et l'incertitude rapportent. Qui prendrait le risque de passer des mois à se creuser les méninges s'il craignait que son merveilleux bidule fonctionne jusqu'à 99 999 mais qu'à partir de 100 001 il ne marche plus ?

[syrac]

J'ajouterai un fait assez éloquent en la matière : pendant des décennies on a entendu les uns et les autres prétendre que la conjecture de Collatz pouvait cesser d'être vraie lorsqu'on le terme initial mettait toute vérification hors de portée du calcul. Et puis les ordinateurs se perfectionnant on a pu explorer des suites basées sur des nombres de plus en plus grands. Et là encore on entendait les mêmes dire : "bon, on a atteint dix mille milliards, mais qui sait, peut-être qu'après ça ne fonctionne plus !". Et ça a continué ainsi avec cent mille milliards, cinq cent mille milliards, etc. etc.

La question qu'on peut se poser est celle-ci : pourquoi les grands nombres n'ont-ils pas eu la délicatesse de donner raison à tous ces messieurs qui doutaient ? Pourquoi n'ont-ils pas revêtu leur costume d'extraterrestre pour leur faire plaisir ?

Une chose est sûre : si la conjecture de Collatz est vérifiée jusqu'à cinq cent mille milliards (chiffre au hasard), alors j'ai encore une bonne marge de sécurité au-dessus de mes petits 99 999.

[nodjim]

De mémoire, il me semble qu'on a testé bien au dela, je crois jusqu'aux nombres à 12 chiffres, voire plus. Mais là n'est pas le problème. Tu as fait un gros travail perso là dessus, on n'en doute pas, et c'est tout à ton honneur. Ce qu'il faut maintenant prouver, c'est que ça marche pour tous les nombres.
Si on n'avait pas prouvé par A+B que les nombres premiers sont en quantité infinie, ce n'est pas parce qu'on en aurait trouvé 1 de 1 milliard de chiffres que pour autant on en aurait déduit qu'il y en a une infinité.
A une certaine époque, on croyait que les nombres de Mersenne étaient premiers ( de la forme 2^(2^k)+1, si je ne m'abuse) jusqu'à ce qu'un matheux plus malin que les autres en ait décomposé un. Et un tel exemple n'est pas unique, qui a rendu les matheux très méfiants avec les hypothèses.
Pour en revenir aux 100 000 premiers nombres testés, c'est moins qu'une goutte d'eau dans l'océan des entiers. Alors il y a encore beaucoup de marges pour les exceptions.
Sinon, j'ai comme toi la conviction que tout nombre redescend à 1. Mais à quoi bon une opinion en math ?

[Ben314]

Perso, ce que je comprend pas, c'est la même chose que Doraki : Quel peut bien être l'intérêt de ton algorithme qui est bien plus compliqué et bien plus long à exécuter que l'algorithme découlant immédiatement de la définition des suites de Collatz ?
Si tu testait directement avec l'algo de base (i.e. ?x3+1 si impair et ?/2 si pair) les entier de 1 à 10^10 (par exemple), ça irait 100 fois plus vite que ton truc pour exactement le même résultat, à savoir que pour le moment, ça marche.

Le seul truc qui me vient à l'esprit, c'est "pourquoi faire simple quand on peut faire compliqué"... :lol3: