Collatz et les puissances de 2

[syrac]

Les résultats ne varient pas quand on teste les 100 000 premiers entiers impairs :



5 = 0,937
85 = 0,0241
341 = 0,0384
5461 = 0,00013

Ces quatre nombres terminaux (sans le 1 final) représentent 0,99946 % des valeurs possibles. Et si on prend en compte 21845 on arrive pratiquement à 100% (0,99996 %).

[nodjim]

Voila la méthode manuelle pour trouver le nombre de puissances de 2 pour un nombre quelconque n.
Le plus simple pour expliquer est de le faire avec un exemple commenté.

Soit 1543:
On fait la division classique par 2, sauf qu'on applique si nécessaire tantôt la partie entière +1, tantôt la partie entière -1.

1543 + (donc 1544)
772 - (indifférent car nombre pair)
386 + (indifférent)
193 - (donc 192)
96 +
48 -
24 +
12 -
6 +
3 -
1 +
1 -
0
ensuite il ne reste plus qu'à faire la différence entre les nombres successifs.

1543 donc 771 nombres divisés que par 2
772 donc 386 nombres divisés que par 4
386 donc 193 nombres divisés que par 8
193 donc 97 nombres divisés que par 16
96 donc 48 nombres divisés que par 32
48 donc 24 nombres divisés que par 64
24 donc 12 nombres divisés que par 128
12 donc 6 nombres divisés que par 256
6 donc 3 nombres divisés que par 512
3 donc 2 nombres divisés que par 1024
1 donc 0 nombre divisé que par 2048
1 donc 1 nombre divisé que par 4096.

Peux tu vérifier avec ton programme ?

[nodjim]

On doit prouver que pour tout entier [latex]n\geq 1[/latex], il existe un entier impair [latex]a_n[/latex] tel que

Prouvons-le par récurrence. La relation est vraie pour n=1 car

Supposons la relation vraie pour un entier [latex]n\geq 1[/latex] fixé. Alors




On pose [latex]a_{n+1}=a_n+ a_n^2\,2^{n+1}[/latex] qui est bien impair.

[syrac]

Il y a un léger problème avec ton système : ce qu'on cherche dans les suites de Collatz c'est la plus grande puissance de 2 qui divise 3n+1, avec n impair et donc 3n+1 pair. Une puissance de 2 ne peut pas diviser un nombre impair, comme ton exemple de 1543.

La méthode manuelle pour un nombre pair c'est de le diviser par 2 jusqu'à obtenir un nombre impair, ce qui tu avoueras est quand même plus simple.

[nodjim]

Oui j'en ai bien tenu compte. 1543, c'est 1543 nombres impairs auxquels on a appliqué 3n +1, puis division par 2.

[syrac]

Oui j'en ai bien tenu compte. 1543, c'est 1543 nombres impairs auxquels on a appliqué 3n +1, puis division par 2.

Ah bon, j'avais pas capté ! Mais j'avoue ne pas bien saisir ta démarche. Pourrais-tu être plus clair ?

[nodjim]

C'est à dire que si tu devais écrire 1543 en binaire, tu ferais la division par 2 en ne prenant que la partie entière du résultat. 1543/2--->771. Ici, tu appliques une alternance de +1 ou -1 pour corriger le nombre impair. Tu commences tjs par un +, puis alternance -+.
1543+: ---->772.
1543-:---->771.

[syrac]

@nodjim

Ce que ton algorithme montre c'est que tu es parti du résultat que j'avais précédemment obtenu pour ensuite essayer de le reproduire sans programmation. Tu pars du nombre n, tu fais n+1 s'il est impair, et tu le divises par 2 jusqu'à obtenir 1.

Si maintenant tu fais n = 20000, le nombre d'itérations dans mon dernier calcul sous Mathematica, il est clair que tu vas obtenir 10000, 5000, 2500, 1250, etc., tout comme moi.

Au final ça ne démontre pas que la probabilité de trouver le diviseur d est de 1/d. Et d'ailleurs est-il nécessaire de le démontrer ? Robot et G.Renault vont nous faire une apoplexie, mais a-t-on besoin de démontrer que le soleil se lève à l'est ?

[Robot]

Au final ça ne démontre pas que la probabilité de trouver le diviseur d est de 1/d. Et d'ailleurs est-il nécessaire de le démontrer ? Robot et G.Renault vont nous faire une apoplexie, mais a-t-on besoin de démontrer que le soleil se lève à l'est ?

Aucun problème, tant que tu ne prétends pas faire des mathématiques.
Le propre des mathématiques est de démontrer.
Mezalor, que fais-tu au juste ?

[syrac]

Voici un aspect intéressant du problème qui consiste à trouver le prédécesseur de n en tant que terme d'une suite impaire. Appelons n1 le prédécesseur de n2. La fonction predN(n2) ci-dessous montre que les puissances de 2 qui divisent les valeurs possibles de 3n1+1 ont toutes un exposant soit pair soit impair.

Dans la liste donnant les prédécesseurs de 5 on trouve des entiers impairs divisibles par 3, ceux-là même que le calcul de Robot par les congruences n'a pas renvoyés, et pour cause, sa méthode se focalise sur les valeurs de n1 non divisibles par 3, ce qui confirme sa validité.

Mais force est de constater que 3, 213, 13653 et d'autres sont des nombres aussi valables que n'importe quel prédécesseur de 5, à cette différence près que leur suite impaire ne compte que trois termes. Il me semble que ceci devrait simplifier le calcul des suites aléatoires. Il suffirait de trouver la raison pour laquelle telle valeur de n2 aura pour prédécesseurs des valeurs de n1 dont l'exposant du diviseur de 3n1+1 est toujours soit pair soit impair. On n'aurait plus besoin de s'assurer que n1 est divisible ou non par 3, et on renverrait la suite telle quelle sans passer par la case ajout de n0 qui peut être divisible par 3. Ça donnerait plus de naturel aux résultats.

[syrac]

Ce que je viens de dire ne tient pas debout. Si on fait suiteAleatoire(50) et qu'on se retrouve avec une suite de trois termes ça va faire désordre. Donc il reste à savoir si on peut prédire quelle sera la parité de l'exposant des diviseurs de 3n1+1.

[nodjim]

A une époque, je m'étais amusé à définir les classes de nombres telles que les valeurs successives données par l'algo restent au dessus du nombre initial. ça donnair un certain nombre de valeurs modulo 2^n. Si la proportion de ces nombres par rapport à 2^n diminue avec l'augmentation de n, ces classes de nombres augmentent toutefois en croissance exponentielle un peu inférieure à 2^n.

Sinon, Syrac, comme je te l'avais dit, la méthode manuelle pour compter les puissances de 2 des "impairs-->3n+1" entre 1 et un nombre donné n'a pas d'autre but que de montrer que c'est faisable à la main, et l'exercice est plaisant.

[syrac]

Aucun problème, tant que tu ne prétends pas faire des mathématiques.
Le propre des mathématiques est de démontrer.
Mezalor, que fais-tu au juste ?

Que Dieu me préserve, surtout pas des mathématiques ! Si c'était le cas je serais assuré de ne jamais trouver la solution du problème de Collatz, comme son historique l'a amplement démontré !

[G.Renault]

Si c'était le cas je serais assuré de ne jamais trouver la solution du problème de Collatz, comme son historique l'a amplement démontré !

Autant je peux comprendre que tu t'amuses à étudier ce problème en faisant des simulations informatiques, autant ta phrase laisse sous-entendre que tu as une chance de trouver une solution à ce problème sans faire de mathématiques, ce qui est absurde.
Et dire que les approches mathématiques n'ont rien donné jusqu'à maintenant ne veut pas dire qu'elles ne donneront jamais rien. Si l'on raisonnait comme cela, aucun problème ne serait résolu à ce jour...

Tu pourras conjecturer tout ce que tu veux (et sans doute plein de choses intéressantes, je n'en doute pas) mais si tu ne fais pas de maths à un moment donné pour appuyer tes idées, tes résultats ne valent rien puisque tu ne sais rien de leur véracité.
La simulation doit être un moyen pour toi de t'orienter vers des pistes de résultats qui te paraissent justes (des conjectures) mais ne doit pas être une fin en soi. L'objectif reste de donner une démonstration de ce que tu crois vrai pour obtenir de réelles avancées sur ce problème.

Bonne chance !

[Robot]

Voici un aspect intéressant du problème qui consiste à trouver le prédécesseur de n en tant que terme d'une suite impaire. Appelons n1 le prédécesseur de n2. La fonction predN(n2) ci-dessous montre que les puissances de 2 qui divisent les valeurs possibles de 3n1+1 ont toutes un exposant soit pair soit impair.

C'est bien, tu constates expérimentalement (ce qui n'est bien sûr pas une preuve) quelques morceaux des propriétés que j'ai démontrées. Bon, c'est un passe-temps inoffensif, mais qu'apportes tu en faisant ça ?

[Sylviel]

C'est bien, tu constates expérimentalement (ce qui n'est bien sûr pas une preuve) quelques morceaux des propriétés que j'ai démontrées. Bon, c'est un passe-temps inoffensif, mais qu'apportes tu en faisant ça ?

Tu aurait tout de même pu commenter mes nombreuses expériences numériques sur ma conjecture : tout nombre entier s'écrit en moins de 100 chiffres ! :ptdr:

[syrac]

autant ta phrase laisse sous-entendre que tu as une chance de trouver une solution à ce problème sans faire de mathématiques, ce qui est absurde.

Je suis depuis longtemps persuadé que la solution de ce problème est beaucoup plus simple qu'on ne le croit. Le fait que tu utilises le mot absurde montre que pour toi c'est un problème extrêmement complexe.

Lors d'une conférence de promotion du livre dans lequel il raconte le processus qui l'a conduit à obtenir la médaille Fields, Cedric Villani a fait la réponse suivante (en substance) à un membre de l’auditoire qui lui demandait s'il était nécessaire de posséder de profondes connaissances en mathématiques pour se lancer dans la recherche d'une solution à un problème : "Non. Il arrive que nos connaissances forment un cadre duquel on est prisonnier. Il est préférable d'aborder un problème avec un esprit neuf, car on peut alors explorer des pistes qu'autrement on n'aurait probablement pas suivies.".

Et dire que les approches mathématiques n'ont rien donné jusqu'à maintenant ne veut pas dire qu'elles ne donneront jamais rien.

Quand ça dure depuis 80 ans on est quand même en droit de se poser des questions. Et ce qui en particulier me conduit à me les poser c'est qu'après tout ce temps on trouve encore des mathématiciens, dont certains sont réputés (je pourrais citer des noms), évoquer ce problème en termes de "durée de vol", de "cycle trivial", et autres inconséquences du genre qui sont et ont toujours représenté une véritable perte de temps. Une fausse piste qu'ont empruntées des générations de mathématiciens et autour de laquelle une littérature incroyablement complexe s'est développée.

Tu pourras conjecturer tout ce que tu veux (et sans doute plein de choses intéressantes, je n'en doute pas) mais si tu ne fais pas de maths à un moment donné pour appuyer tes idées, tes résultats ne valent rien puisque tu ne sais rien de leur véracité.
La simulation doit être un moyen pour toi de t'orienter vers des pistes de résultats qui te paraissent justes (des conjectures) mais ne doit pas être une fin en soi. L'objectif reste de donner une démonstration de ce que tu crois vrai pour obtenir de réelles avancées sur ce problème.

Tout à fait d'accord sur ce point. C'est la raison pour laquelle je m'adresse à des mathématiciens confirmés, avec l'espoir qu'ils fassent autre chose que de me prendre de haut parce que je n'appartiens pas à leur caste.

[G.Renault]

Le fait que tu utilises le mot absurde montre que pour toi c'est un problème si complexe qu'il est hors de portée d'un amateur.

Je n'ai pas dit qu'il était absurde que tu résolves le problème mais que tu le résolves sans faire de maths.
Car une démonstration, ce sont des maths.

Quand ça dure depuis 80 ans on est quand même en droit de se poser des questions.

Se poser des questions oui, affirmer que faire des maths ne résoudra pas le problème est une tout autre histoire. Et pour la durée, c'est pas énorme non plus. Le grand théorème de Fermat est quand même un cas d'école dans ce domaine.
Ce qui est plus surprenant, c'est le fait que ça résiste malgré la simplicité de l'énoncé.
Et ce qui est amusant, c'est justement cette simplicité d'énoncé qui permet déjà de faire des tests et de s'amuser avec un bagage mathématique de collégien (je ne parle pas de toi bien évidemment, je compare avec les connaissances de mes élèves).

Mais bon en soit, je trouve que ce genre de problèmes se rapproche un peu de l'étude des nombres premiers. Il se passe un truc, encore et encore, et on ne sait pas pourquoi ça se passe encore et encore...

Tout à fait d'accord sur ce point. C'est la raison pour laquelle je m'adresse à des mathématiciens confirmés, avec l'espoir qu'ils fassent autre chose que de me prendre de haut parce que je n'appartiens pas à leur caste..

Tu n'as jamais formulé la moindre demande dans tes posts. Tu exposes tes idées ou tes simulations et les membres du forum te répondent ce qu'ils en pensent.
Si c'était vraiment ta démarche, tu rebondirais sur les démonstrations qui te sont faites et tu demanderais des explications sur les points obscurs pour progresser sur l'aspect théorique et te donner des idées nouvelles pour tes simulations. Non ?

Les mathématiques ne sont pas une caste, juste une manière de penser qui fait appel à la logique et à laquelle il t'appartient d'adhérer ou non...

[Robot]

Bah, le discours habituel des pauvres génies incompris que la caste des mathématiciens englués dans leurs certitudes refuse de reconnaître à leur juste valeur ... C'est banal, ça se rencontre assez fréquemment sur les forums.

[G.Renault]

Moi je trouve ta démarche plutôt sympa. Elle m'a permis de me mettre à réfléchir (enfin) à ce problème de manière un peu poussée par l'intermédiaire de l'étude de tes algorithmes et de ton approche.

Il est simplement dommage que tu n'essaies pas de comprendre l'aspect mathématique des réponses qui te sont faites pour essayer, toi aussi, de progresser dans l'étude de ce problème.