Collatz et les puissances de 2

[G.Renault]

Permets-moi d'en douter. Je me suis livré à une étude statistique portant sur la probabilité de rencontrer tel diviseur dans une suite impaire. Si d est ce diviseur, ou puissance de 2, elle est égale à 1/d. Tu as en conséquence une chance sur 2048 de tomber sur 2048, qui ne figure pas dans ma liste de diviseurs (mais qu'on peut facilement ajouter). De plus, du moins jusqu'à preuve du contraire, tu as toujours le choix entre 3, 4 voire plus de diviseurs. Il y en a donc toujours un qui fera l'affaire.

En fait tu confonds le « presque sûr » avec le « certain ».
Quel est le rapport entre ce qu'on te dit et le fait que tu connaisses la probabilité que 2048 apparaîsse dans une suite impaire ? En quoi cela t'assure-t-il que ton algo va renvoyer une liste non vide ?

On est d'accord, il y a toujours un diviseur qui fera l'affaire, mais tu ne sais pas s'il est dans ta liste avant de lancer ton algo.

[G.Renault]

Ce à quoi j'ajouterai que oui, le cas est envisageable où pour des valeurs très grandes de n l'algorithme ne trouve pas de diviseur adéquat dans la liste préétablie. Mais je le répète, la probabilité d'un tel évènement est extrêmement faible.

Ah bah voilà... Donc tu es d'accord avec nous. Donc, il n'y a pas de débat...

En passant, j'aimerais bien savoir combien vaut cette probabilité et comment tu l'obtiens.

[Robot]

Je répète que non, ce n'est pas envisageable si l'on s'autorise 2,4,8,16 et que c'est prouvé.

[syrac]

Je te renvoie à mon précédent message, que j'ai posté en même temps que toi.
Ton message précédent que j'ai déjà lu n'a rien à voir avec ce que je t'explique...

Avec l'autre approche, tu en es sûr puisque tu as explicité pour chaque étape et pour n'importe quel k, des candidats qui fonctionnent.
Tu saisis la nuance ?

Parfaitement, mais cet algorithme a seulement une vocation pratique.

Pour en revenir à la probabilité de rencontrer tel diviseur, je me suis livré à cette étude après avoir réalisé que la seule possibilité pour une suite impaire de croître était que le diviseur de 3n+1 soit 2. A partir de 4 le successeur de n sera plus petit que lui. L'idée était de savoir si statistiquement une suite a tendance à croître ou à décroître. Or, la somme 1/4+1/8+1/16+1/32+1/64+... tend vers 1/2, si bien que les suites de Collatz ne tendent ni à croître ni à décroître.

EDIT : j'ai obtenu ces résultats en calculant des dizaines de milliers de suites et en comptant à chaque fois combien elle contenait de diviseurs 2, 4, 8, etc.

[syrac]

Pardon, les suites de Collatz ne devraient pas tendre à croître ou à décroître.

[G.Renault]

Je répète que non, ce n'est pas envisageable si l'on s'autorise 2,4,8,16 et que c'est prouvé.

Oui mais là on se plaçait dans le cadre de l'algo de Syrac. Ne me fais pas dire ce que je n'ai pas dit.

[syrac]

En fait c'est assez étrange. J'aurais peut-être dû dire que les suites de Collatz, prises dans leur ensemble, n'ont aucune tendance à la croissance ou à la décroissance. Mais là on aborde la métaphysique...

[syrac]

Je viens de faire un test simple dans Mathematica, que voici (explications après l'image) :



On calcule 3n+1 pour les 1000 premières valeurs impaires de n, puis on calcule la plus grande puissance de 2 qui divise chaque résultat.

La fonction Counts renvoie les éléments différents que cette liste contient, et leur fréquence. On voit que 2 apparaît une fois sur 2, que 4 apparaît une fois sur 4, que 8 apparaît une fois sur 8, etc.

[syrac]

Il est clair que ce résultat n'est qu'un approximation. Pour avoir des résultats plus précis il aurait fallu faire ce test pour des dizaines de milliers d'entiers impairs.

[syrac]

Voici les résultats pour les 5000 premières valeurs impaires de n :

[nodjim]

Tu sais, il n'y a pas vraiment besoin d'informatique pour calculer ça.

[syrac]

Tu ne fournis aucune preuve qu'il n'y a pas de liste vide.
Par contre, le raisonnement que j'ai fait prouve qu'on peut avoir une liste vide si on se contente de 2,4,8, tandis qu'on est sûr qu'il n'y a pas de liste vide si on prend 2,4,8,16.

Réponse suffisamment ambiguë pour qu'on s'y arrête. Toi et G.Renault ne cessez de dire que le diviseur requis pourrait ne pas figurer dans la liste préétablie, ce que j'admets (avec les réserves conséquentes aux probabilités), et voilà que par magie le simple fait d'ajouter 16 à la liste 2,4,8 prouve que ce cas ne peut plus se produire !

Dans ce cas, pourquoi le fait d'ajouter 2048 à 2, ..., 1024 ne règle-il pas là-aussi le problème ?

[syrac]

Tu sais, il n'y a pas vraiment besoin d'informatique pour calculer ça.

Ce que tu vas t'empresser de démontrer je suppose ? :lol3:

[nodjim]

Ah pardon, je confondais les impairs qu'on divise par 2, et ça c'est élémentaire, avec les mêmes nombres qu'on a d'abord multiplié par 3 (+1).
C'est un problème intéressant. Il n'y a pas beaucoup d'écart avec les impairs originaux, sauf qu'on divise un peu plus loin évidemment.
Y a peut être quelque chose à creuser de ce coté là, pas pour résoudre la conjecture, loin s'en faut, mais juste en tant que problème indépendant.

[G.Renault]

et voilà que par magie le simple fait d'ajouter 16 à la liste 2,4,8 prouve que ce cas ne peut plus se produire !

Parce que peu importe la valeur de k, il existe une de ces 4 puissances qui fonctionnera, ce que montre la liste des congruences de k modulo [9] établie par Robot.

[syrac]

Voici pour les 20 000 premiers entiers impairs. Cette fois-ci je trie le résultat, ce qui améliore sa lisibilité :



On voit que dans 19375 cas sur 20000, soit dans 97% des cas, le diviseur ne dépasse pas 32.

[Robot]

Ce que tu vas t'empresser de démontrer je suppose ? :lol3:

La démonstration du fait que parmi les entiers n tels que 2^k divise 6n+4, un sur deux est tel que 2^{k+1} divise 6n+4 est très facile.
Donc oui, il n'y a pas besoin de faire des tests pour trouver les fréquences : une bonne démonstration mathématique suffit.

Mais tu as l'air fâché avec les démonstrations, et tu n'as pas l'air de comprendre ce que ça veut dire de prouver qu'on peut toujours remonter dans la suite de Collatz impaire avec 2,4,8,16, tandis qu'on ne peut pas avec 2,4,8.

[syrac]

Mais tu as l'air fâché avec les démonstrations

Disons que si j'étais un scientifique ce serait de préférence dans le domaine des sciences appliquées plutôt que dans celui des sciences théoriques.

Merci de ne pas me répondre que même dans ce cas je devrais avoir un solide bagage, ce n'était qu'une image.

[Robot]

Bon, ben je crois que tout a été dit. Bonne nuit ...

[syrac]

Bon, ben je crois que tout a été dit. Bonne nuit ...

Merci, bonne nuit à toi !

Voici les statistiques pour l'avant-dernier terme d'une suite impaire :



La probabilité de tomber sur

5 = 0,937
85 = 0,0247
341 = 0,0381
5461 = 0,00012

Ceux qui ont programmé la fonction suiteAleatoire[N] dans Mathematica pourront s'ils le veulent modifier les poids en conséquence dans la variable dL (pour 16, 256 1024 et 16384).

En d'autres termes, pratiquement toutes les suites générées se termineront par 5, 1. On peut évidemment modifier ces chiffres pour donner plus ou moins de chances aux autres candidats.