Collatz et les puissances de 2

[G.Renault]

le processus est continu, il ne fonctionne pas par essais successifs.

Justement c'est là-dessus que je mets un petit bémol. C'est pour ça que j'ai écrit le mot TEST en gros plusieurs fois car les essais successifs, ce sont justement des tests de divisibilité par 3 (ou qui s'en rapprochent). Or, ces tests, tu les fais aussi, de manière un peu cachée dans ton programme, lorsque tu testes si l'expression n0 est un entier pour tes 24 valeurs de x.
Alors je suis d'accord que ton expression est carrément plus simple à implémenter dans un programme qu'un algo de Collatz à l'envers mais je ne crois pas que tu t'affranchisses réellement de ces fameux essais successifs.

Pour ton programme, je ne vois pas pourquoi tu veux à tout prix calculer t1+t2. Tu as fait un choix arbitraire en décidant de fixer le p au départ et de faire varier la puissance dans le t1 pour obtenir tes candidats n0.
Pourquoi ne testes-tu pas, dans tes t1,t2,...,tk tous les exposants inférieurs à un nombre que tu fixes (arbitrairement lui aussi) ?
Car tu as simplifié n0 mais l'expression ressemble à ça à la base :
(ouais bon là c'est pas super lisible...)

Du coup pourquoi ne pas écrire un truc du genre :

* Demander N et un entier de "contrôle" e pas trop grand (on prend 4 par exemple)...
* Créer un N-1 uplet nommé K (contenant les exposants pi)
* Pour chaque i dans {1,...,N-1}, K[p]=1 (le i-ème élément du N-1 uplet)
Bon et là j'ai cherché un peu mais je bloque sur une implémentation dans un programme et je n'ai plus trop les idées claires...
Mais bon le principe, c'est simplement de tester si la valeur illisible plus haut est un entier (donc un n0) pour les N-1 uplets
(1,1,...,1,1)
(1,1,...,1,2)
(1,1,...,1,3)
(1,1,...,1,4) (4 est la valeur de contrôle dans l'exemple...)
(1,1,...,2,1)
(1,1,...,2,2)
(1,1,...,2,3)
(1,1,...,2,4)
(1,1,...,3,1)
et ainsi de suite jusqu'à (4,4,...,4,4).
Cette progression des N-1 uplets doit bien s'implémenter d'une manière ou d'une autre...

[G.Renault]

En fait, pour poser une question simple :

- Pourquoi choisis-tu de fixer p (donc son exposant qui vaut par exemple p1+p2) et de faire varier ensuite l'exposant de t1 (ton x que je viens d'apeller p2) entre 1 et p1+p2-1 ?

- Tu aurais tout aussi bien pu tester tous les p1 et p2 entre 1 et 10 par exemple. Tu aurais alors des solutions que ton algorithme ne peut pas trouver.

[G.Renault]

Et pour rebondir encore, c'est pour cela que je te dis que si tu n'explicites pas vraiment ce que tu cherches, tu ne sauras jamais vraiment dans quelle direction aller.

Ici, tu parlais d'application intéressante de ton approche pour écrire un algo renvoyant des n0 de suites impaires à 3 termes.
Alors, certes ça peut être intéressant A CONDITION que tu expliques en quoi c'est mieux qu'un algo qui ferait Collatz à l'envers : plus rapide ? plus simples à écrire (mais cet argument n'est pas super dans le sens ou il vaut mieux un algo compliqué qui donne un résultat puissant qu'un algo simple qui donne un résultat moindre) ? plus de n0 dans la réponse ?...

Tu peux en fixer plein des conditions de ce genre :
- Je veux un algo qui prend en argument N et qui retourne le plus rapidement possible (donc en faisant le moins de calculs possible) un n0 d'une suite de N termes.
- Je veux un algo qui prend en argument N et un nombre p et qui me renvoie p nombres n0 correspondant à des suites de N termes.
- Je veux un algo qui prend en argument N et un nombre impair k et qui me renvoie TOUS les n0 inférieurs à k possibles qui correspondent à des suites de N termes. Et là encore, tu dois exiger un argument de vitesse sans quoi il te suffit de faire l'algo de Collatz pour tous les impairs inférieurs à k, de repérer les suites de N termes et de renvoyer les n0 correspondants.

Ou sans parler d'algo :
- Je cherche une formule me donnant le nombre de suite impaires de N termes que je peux obtenir en utilisant seulement, pour mes di, des puissances de 2 plus petites ou égales à 2^4 par exemple...
- etc etc...

[syrac]

Là encore je pense que mes explications n'étaient pas claires et qu'il serait bon d'expliciter ce qu'est la somme t1+t2+...+tk. Voici le tableau figurant en haut de la page 4 de mon papier :



Dès la première page j'ai posé p = S + 3^(N-2) (3n0+1). S est la somme des tk, et dans le tableau ci-dessus p est la somme des valeurs de rangee X listeP3 calculées par récurrence, et par définition une puissance de 2. C'est justement parce que p devient cette puissance de 2 après un certain nombre d'étapes que le dernier terme d'une suite de Collatz est 1.

Le dernier terme de rangee X listeP3 est 3^(N-2) (3n0+1), ce qui dans l'exemple de n0 = 29 donne 3^4 * 88 = 7128, si bien qu'on peut écrire S sous la forme 512+192+144+216. Or, chacun de ces nombres est le produit d'une puissance de 2, dans rangee, par une puissance de 3, dans listeP3. Ils sont les termes de la somme t1+t2+t3+t4, qui en compte N-2.

S'il est aussi facile de calculer des valeurs de n0 dont la suite impaire compte trois termes, ce que fait la fonction suite3termes(e), c'est parce que t1, 512 dans l'exemple, est le produit d'une puissance de 2 par 3^0, c'est-à-dire une puissance de 2. Mais ce n'est plus le cas des termes t2, t3, ..., tk, d'où la difficulté de les calculer sinon par un nombre de boucles imbriquées dont le nombre croîtrait avec N.

L'expression de n0 fonction de p et de N, si elle paraît simple, est en réalité un véritable casse-tête. Si on sait que les puissances de 3 figurent dans leur ordre naturel, ce n'est pas du tout le cas des puissances de 2, qui sont quelconques (lorsqu'on ne les connaît pas pour avoir calculé le tableau ci-dessus, bien sûr).

Lorsqu'on cherche des valeurs de n0 qui produisent une suite impaire de 3 termes, on ne tient compte que de t1. Pour 4 termes on doit tenir compte de t1+t2, de t1+t2+t3 pour 5 termes, etc. La difficulté s'accroît avec N.

C'est pour ça que j'ai écrit le mot TEST en gros plusieurs fois car les essais successifs, ce sont justement des tests de divisibilité par 3 (ou qui s'en rapprochent). ... mais je ne crois pas que tu t'affranchisses réellement de ces fameux essais successifs.

Chaque itération de l'algorithme utilisé par la fonction suiteAleatoire(lg) choisit le diviseur précédent aléatoirement, afin de construire la suite par la fin. Il est évident que parmi les diviseurs 2 à 1024 disponibles, certains d'entre eux seulement fonctionneront à une étape donnée. Le seul critère requis est que le terme de la suite qui découlera du choix de tel ou tel diviseur ne soit pas divisible par 3. Il est de ce fait nécessaire de le tester, sinon on se retrouverait avec une suite composée de fractions et dans laquelle tout terme entier serait le fait du plus pur des hasards. Une fois ce test passé on passe au calcul du terme précédent, jusqu'à ce que le nombre de termes calculés soit égal au paramètre lg passé à la fonction, donc dans un processus continu, qui ne procède pas à la recherche d'une suite de lg termes en en calculant de nombreuses jusqu'à ce qu'il finisse par tomber sur une qui satisfasse à ce qu'on lui a demandé.

EDIT : d'ailleurs ceci pose une question intéressante : pourquoi certaines puissances de 2 seulement sont-elles de bons candidats à chaque étape ? Quelle est la relation entre un diviseur et celui qui le précède ? Si on la découvrait alors on pourrait se passer du test en question.

[syrac]

Je viens de m'apercevoir d'un petit problème avec la fonction suiteAleatoire(). J'ai en effet écrit :

While[!MemberQ[{1, 5},Mod[m1, 6]], …] signifie qu’on continue de tirer un diviseur au hasard aussi longtemps que la variable m1 n’est pas un entier impair non divisible par 3.

La conséquence en est que le premier terme de la suite renvoyée ne sera jamais un entier impair divisible par 3, alors que n0 peut tout à fait l'être. Modifier ce comportement entraînerait une complexification de l'algorithme.

[Robot]

Tirer au hasard et tester, bof.

Remontée de la suite de Collatz :

Soit un entier impair, non divisible par 3. On caractérise les entiers tels que soit de la forme où est un entier impair non divisible par 3, c.-à-d. ou . On veut donc ou , soit ou .

On travaille dans le groupe multiplicatif de qui est un groupe cyclique d'ordre 6 engendré par la classe de 2. On a la réponse suivant la classe de modulo 9 :
Si , on prend ou .
Si , on prend ou .
Si , on prend ou .
Si , on prend ou .
Si , on prend ou .
Si , on prend ou .

On a bien sûr plus de choix pour arriver au premier terme à qui on demande juste d'être impair, on prend pair si et impair si

[syrac]

Voici l'algorithme modifié. Il renvoie maintenant une suite impaire du nombre exact de termes demandé, passé par le premier paramètre N. Selon la valeur du second paramètre, d, la fonction renvoie la suite (1, par défaut), les diviseurs (2) ou les deux (3). Le premier terme de la suite renvoyée peut être divisible par 3.

Tirer au hasard et tester, bof.

Tu ne peux pas balayer d'un revers de main l'idée de choisir les diviseurs aléatoirement. On ne peut tout simplement pas faire autrement. Voici comment une suite impaire est calculée depuis son avant-dernier terme, celui qui précède 1. On commence par choisir aléatoirement le dernier diviseur, qui peut être 16, 256, 1024 ou 16384 (mais rien n'interdit d'allonger cette liste), puis on calcule le terme impair qui précède l'avant-dernier :



L'indice r représente le rang d'un terme impair, et bien sûr r-1 le rang du terme impair qui le précède. Avant d'entrer dans la boucle While on choisit au hasard la valeur du dernier diviseur, m1, puis on calcule la valeur de l'avant-dernier terme impair de la suite, m2, égal à (m1 - 1)/3. Avec m1 = 16 on aura m2 = 5. Terminé pour l'avant-dernier terme.

Pour connaître la valeur du prédécesseur de m2 on doit produire un diviseur d aléatoirement en sorte que (m2*d - 1)/3 soit un entier impair non divisible par 3, par exemple 32 puisque (5*32 - 1)/3 = 53. Voyons quelles possibilités nous sont offertes :

Avec 2 on aurait obtenu (5*2 - 1)/3 = 3, divisible par 3.
Avec 4 on aurait obtenu (5*4 - 1)/3 = 19/3.
Avec 8 on obtient (5*8 - 1)/3 = 13, ok.
Avec 16 on aurait obtenu (5*16 - 1)/3 = 79/3.
Avec 32 on obtient (5*32 - 1)/3 = 53, ok.
Avec 64 on aurait obtenu (5*64 - 1)/3 = 319/3.
Avec 128 on aurait obtenu (5*128 - 1)/3 = 213, divisible par 3.
Avec 256 on aurait obtenu (5*256 - 1)/3 = 1279/3.
Avec 512 on obtient (5*512 - 1)/3 = 853, ok.
Avec 1024 on aurait obtenu (5*1024 - 1)/3 = 5119/3.

On avait donc le choix entre 8, 32 et 512, mais on ne pouvait pas le savoir sans passer par le test que tu sembles remettre en cause.

Le problème ne consiste donc pas à trouver le moyen de produire un entier impair non divisible par 3 sans avoir à le tester, mais de savoir si un diviseur choisi aléatoirement produira, dans le contexte cité, un tel entier.

[Robot]

Bon, visiblement tu n'as rien compris de ce que j'ai écrit.

Reprenons le cas de 5 : 5 est bêtement congru à 5 modulo 9. On connaît donc a priori, et sans avoir besoin de tester, toutes les puissances de 2 qui, multipliées par 5, donnent un entier de la forme 3m+1 où m est un entier non divisible par 3. Ce sont les et (voir le petit tableau que j'ai écrit), autrement dit 8, 32, 512, 2048, , , , ...

Pour remonter 1 on a le choix entre tous les et , en enlevant le premier qui fait stationner à 1.

La caractérisation que j'ai donnée (qui repose sur des calculs modulaires élémentaires et est forcément déjà bien connue) permet par exemple de compter le nombre de vols impairs de longueur N où les puissances de 2 qui interviennent sont inférieures ou égales à . Je te laisse faire l'exercice. :lol3:

Ton "On avait donc le choix entre 8, 32 et 512, mais on ne pouvait pas le savoir sans passer par le test que tu sembles remettre en cause" montre à l'évidence :
- soit que tu ne lis pas,
- soit que tu ne comprends pas ce que tu lis.

[G.Renault]

La caractérisation que j'ai donnée (qui repose sur des calculs modulaires élémentaires et est forcément déjà bien connue)

C'est la caractérisation que j'avais utilisée pour calculer à la main mes remontées de suites de Collatz. Mais je m'étais limité aux puissances inférieures à et je n'avais que la caractérisation par rapport à 3 en testant ensuite à la main si les m étaient divisibles par 3.
Ma foi, ta caractérisation par 9 est très clairement présentée !

Je pense cependant que tu oublies (ou passes sous silence) le cas pathologique ou .
Dans ce cas, pour , il faut exclure qui renvoie une suite de 2 termes impairs qui sont 1 et 1.
De même, si l'on veut des suites de termes avec , on a un seul choix pour la première remontée ( est exclu), et ensuite on a deux choix pour chaque remontée.

Ce qui donnerait pour les puissances de 2 inférieures ou égales à :

- pour : suites de Collatz de N termes
- pour : suites de Collatz de N termes

J'ai bon ?

On peut aussi compter pour les puissances inférieures à mais pour les puissances inférieures à , c'est une autre histoire...

Pour Syrac, j'ai remarqué aussi que tu réponds aux posts en réexpliquant tes algorithmes comme si on ne les comprenait pas au lieu d'essayer de rebondir sur nos explications ou de souligner d'éventuelles erreurs dans nos messages, ce qui n'est pas très constructif.

[Robot]

Je pense cependant que tu oublies (ou passes sous silence) le cas pathologique ou .
Dans ce cas, pour , il faut exclure qui renvoie une suite de 2 termes impairs qui sont 1 et 1.

Euh... n'as-tu pas lu

Pour remonter 1 on a le choix entre tous les et , en enlevant le premier qui fait stationner à 1.

?

Ce qui donnerait pour les puissances de 2 inférieures ou égales à :

- pour : suites de Collatz de N termes
- pour : suites de Collatz de N termes

J'ai bon ?

Déjà, pour moi la longueur est le nombre de termes moins un (histoire de piquets et d'intervalles). Ensuite, pour une longueur (en ce sens) , je compte .

[G.Renault]

Ah bah non cette phrase était sortie de ma tête.

Oui tu as raison pour ton décompte, je ne sais pas pourquoi je ne retenais qu'une valeur de p à chaque fois...

[syrac]

Bon, visiblement tu n'as rien compris de ce que j'ai écrit.

Pour Syrac, j'ai remarqué aussi que tu réponds aux posts en réexpliquant tes algorithmes comme si on ne les comprenait pas au lieu d'essayer de rebondir sur nos explications ou de souligner d'éventuelles erreurs dans nos messages, ce qui n'est pas très constructif.

Il est vrai que mes notions en matière de congruences sont basiques. Je ne me penche sérieusement sur un aspect des mathématiques que lorsque le besoin s'en fait sentir, et il semble que ce soit maintenant le cas des congruences.

En attendant que j'étudie la question de plus près, si vous m'expliquiez concrètement, d'un point de vue algorithmique, en quoi cette approche permet de contourner la nécessité de choisir au hasard le prédécesseur d'un terme d'une suite impaire dans le but de construire une suite aléatoire par la fin ?

Supposons que je puisse savoir, sans avoir à procéder à des tests, quelles puissances de 2, d, utiliser dans l'expression (n*d-1)/3 ; quel est le gain en ce qui concerne l'algorithme ? Je devrai à chaque étape commencer par déterminer quelles sont les valeurs adéquates du prédécesseur de n puis en choisir une au hasard. Alors qu'est-ce que ça change ?

[Robot]

Je te rappelle ce que tu as toi-même écrit :

On avait donc le choix entre 8, 32 et 512, mais on ne pouvait pas le savoir sans passer par le test que tu sembles remettre en cause.

Tu pourrais au moins reconnaître que c'est faux !

Bon, continue à t'amuser, ça ne fait pas de mal même si ça n'avance pas à grand chose. Ca serait effectivement une bonne idée, si tu veux progresser, d'en apprendre un peu plus sur les congruences.

[syrac]

Oui, je reconnais que "on ne pouvait pas le savoir sans passer par le test ..." est faux, puisque tu apportes une autre solution. Mais de ton côté, tu dois aussi reconnaître que pour parvenir au même résultat tu as besoin de connaître également ces fameux 8, 32 et 512. Et cette approche est même plus compliquée (du point de vue de l'algorithme) parce que tu dois choisir entre les valeurs que tu as calculées pour chaque valeur de n, alors que la forme présente de mon algorithme choisit entre des valeurs non calculées, c'est-à-dire la suite préétablie des puissances de 2 jusqu'à 1024.

[G.Renault]

En attendant que j'étudie la question de plus près, si vous m'expliquiez concrètement, d'un point de vue algorithmique, en quoi cette approche permet de contourner la nécessité de choisir au hasard le prédécesseur d'un terme d'une suite impaire dans le but de construire une suite aléatoire par la fin ?

En fait tu ne t'affranchis pas des tests car tu dois tester k, sauf qu'une fois que tu l'as testé, tu peux choisir une valeur au hasard dont tu sais à coup sûr qu'elle va marcher.
Toi, tu choisis au hasard des puissances de 2, puis tu les testes. Comme tu ne sais pas à l'avance quelles valeurs vont fonctionner, tu te fixes une plage de candidats arbitrairement grande. Or, il se peut parfaitement qu'aucun candidat de ta plage ne permette de remonter à l'étape précédente.

Supposons que je puisse savoir, sans avoir à procéder à des tests, quelles puissances de 2, d, utiliser dans l'expression (n*d-1)/3, quel est le gain en ce qui concerne l'algorithme ? Je devrai à chaque étape commencer par déterminer quelles sont les valeurs adéquates du prédécesseur de n puis en choisir une au hasard. Alors qu'est-ce ça change ?

Ca change que tu es absolument certain de trouver une valeur qui fonctionne, et donc d'avoir un algorithme qui te renvoie la suite (ou le n0) tant désirée.
Ce n'est pas le cas de ton algorithme qui peut parfaitement te renvoyer une liste de réponses vide.

Donc oui dans un cas, tu peux écrire un algorithme simple mais dont tu ne sais pas à l'avance s'il te donnera une réponse (dans ce cas tu devras le lancer pour d'autres valeurs de p).
Dans l'autre cas, l'implémentation est plus difficile (mais possible) mais te renvoie une solution à coup sûr.

[syrac]

Toi, tu choisis au hasard des puissances de 2, puis tu les testes. Comme tu ne sais pas à l'avance quelles valeurs vont fonctionner, tu te fixes une plage de candidats arbitrairement grande. Or, il se peut parfaitement qu'aucun candidat de ta plage ne permette de remonter à l'étape précédente.

Je te renvoie à mon précédent message, que j'ai posté en même temps que toi.

Ce n'est pas le cas de ton algorithme qui peut parfaitement te renvoyer une liste de réponses vide.

Ah bon ? Peux-tu citer un seul cas de liste vide ?

[Robot]

Ah bon ? Peux-tu citer un seul cas de liste vide ?

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.

[syrac]

Or, il se peut parfaitement qu'aucun candidat de ta plage ne permette de remonter à l'étape précédente.

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.

[G.Renault]

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...

Ah bon ? Peux-tu citer un seul cas de liste vide ?

Ta question est hors-sujet, je n'en connais pas et n'ai pas envie d'en chercher. Il n'en existe peut-être pas d'ailleurs si tu prends des plages de 2^n avec suffisamment d'éléments chaque fois que tu fais ton algorithme. Le point important est que toi, tu ne peux pas être sûr à l'avance que ta liste ne sera pas vide car tu ne l'as jamais prouvé. Il se peut que parmi tous tes candidats, aucun ne renvoie une valeur de n0 entière.
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 ?

[syrac]

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.