Je connais la suite jusque 427: [23183781049, 714]. Les éléments de ce dictionnaire Python sont composés d'une clé, T, et de ses deux valeurs associées, sous forme d'une liste : la plus petite valeur de n0 (impair) dont la suite compressée est de type T, et la longueur de celle-ci.
On peut oublier la clé T, qu'il suffit d'incrémenter à chaque nouveau calcul, ainsi que la longueur de chaque suite. Ce qu'il faudrait trouver c'est la règle ou formule qui définit la relation entre les termes successifs de la suite composée des valeurs de n0, c'est-à-dire 17, 11, 7, 9, 25, 33, 43, 57, 39, 105, 135, 185, 123, 169, 219, 159, 379, 283, 377, 251, etc.
Je ne peux pas croire que c'est le chaos total, qu'il n'existe aucune règle. Il existe nécessairement une méthode de calcul de la plus petite valeur de n0 dont la suite compressée est de type donné. Enfin c'est ce que je crois. Je pourrais poursuivre avec la recherche exhaustive et faire tourner un ordinateur pendant 10 ans pour arriver à T = 1000 (ou beaucoup moins avec un supercalculateur). Mais je pense que trouver une formule donnerait un nouvel éclairage à la structure dont j'ai parlé plus haut, et qui permet de faire les calculs dont j'ai donné quelques exemples.
Je rappelle toutefois que je parle de suites compressées, alors que toi tu t’intéresses aux suites standard. Or, ce dont il est question ici ne s'applique pas à ces suites, qui sont très différentes des suites compressées (il existe par exemple beaucoup moins de suites standard de longueur donnée que de suites compressées).
PS : pour arriver à 427 il m'a fallu calculer la suite compressée de chaque entier impair jusqu'à 23 183 781 049, ainsi que son type. La valeur du plus petit n0 de type 426 était 17 387 835 787. Il a donc fallu (23183781049 - 17387835787) / 2 = 2 897 972 631 itérations supplémentaires pour trouver le n0 suivant. Et cet écart ne fait que croître.
@Wilfrid Merci pour toutes ces explications. Cette liste de n0, 17, 11, 7, 9, 25, 33, 43, 57, 39, 105, 135, 185, 123, 169, 219, 159, 379, 283, 377, 251, correspond exactement à l'incrémentation de e à partir de 3. En ce cas, on trouve un n0 en cherchant la plus petite valeur de x pour un e donné. Par exemple, 17 est en e = 3 et x = 12, 11 en e = 4 et x = 14. Je peux donc te proposer la liste suivante pour e <=125
Mais attention à un point. Il existe régulièrement plusieurs impairs possibles pour un même n0. Par exemple 185, 187 et 191 sont tous en e=14 et x = 44.
84383, 85673, 86175, 88135, 89023, 89263, 89855, 92713, 94959 sont tous en e = 110 et x = 301. Donc un n0 est le plus petit impair dont la valeur e correspond au plus petit x possible. Donc n0 est le plus petit impair d'un cluster dont la valeur e correspond au plus petit x possible. Mais cela marche aussi pour e = 1 ou e = 2. Pour e = 1, on a 5 avec x = 5 Pour e = 2, on a 3 avec x = 7
"La règle ou formule qui définit la relation entre les termes successifs de la suite composée des valeurs de n0" est la suivante. À partir de 1, on incrémente e pour trouver une valeur minimale de x pour une valeur minimale de i. Par rapport à la formule de @Collag3n $x=\lceil e \log_26 + \log_2i \rceil$ avec e = 3. Pour i : 15, 17, 19, 21, 23, 25, x varie de 11.66 à 12.399 donc 6 candidats pour x = 12 Mais pourquoi choisir x = 12 et i = 17 ??? Le graphique montre en orange les n0 parmi les 1878 impairs pour x<=34
@Wilfrid Comment veux-tu que je triche ? Je reprend les explications : D'abord et toujours on génère une liste d'impairs en partant de 2^4. Instruction 1 : doubler tous les éléments du set précédent Instruction 2 : extraire tous les i = (p-1)/3 du set précédent. Chaque set correspond à une puissance de 2 donc à un x. La liste des impairs que l'on obtient a donc un ordre qui lui est propre, et on peut associer chaque i à un x, et à un h = arrondi(log2(i)), ou simplement à log2(i). Quand on affiche les données x, log2(i), on a le graphique de mon post précédent. Il faut comprendre que la variable e, cad le nombre d"étapes impairs (i de départ inclus), est répresentée dans ce graphique par les alignements diagonaux, en partant de e = 1 à l'extrême gauche. On peut donc constuire des clusters pour chaque i de coordonnées {h, e, x} Tes n0 sont les plus petits impairs en bas de chaque diagonale. Donc pour les trouver, il suffit de partir de e = 1, puis de chercher quel est le plus petit impair ayant le plus petit x parmi les 1878 impairs générés pour x=34. On incrémente ensuite e jusqu'à 11 qui est la valeur max pour x = 34.
Si on veut produire une liste plus longue, c'est impossible pour moi de faire une liste avec x>34 (à cause du VBA.... script Python serait bienvenu au cas où...). Donc on fait autrement en générant les impairs dans l'ordre arithmétique et en calculant h, e, et x à partir des données des suites de Collatz (non compressées et que je tronque à 16). Je trouve mon x en ajoutant 3 au nombre total d'étapes paires ou impaires, i de départ et 16 inclus. J'ai fait un calcul jusqu'à i = 100001 ce qui donne parmet d'atteindre h = 17. Cette liste permet de trouver tes n0 pour e <=125. Mais cette liste n'est pas la vraie liste que l'on obtient avec les 2 instructions. C'est une sorte d'ersatz qui suffit pour certaines choses mais pas pour tout.
Pas du tout. Je te demandais une méthode de calcul, un algorithme, pas un cours. Je t'ai souvent dit que tu ne savais pas t'expliquer, mais là c'est le pompon !
Imagines que tu expliques ta méthode à un enfant de 12 ans, et pas à quelqu'un qui a fait ça toute sa vie. Ça aidera certainement.
1) on ne peut rien faire tant que la liste d'impairs provenant de l'algoritme n'est pas produite (à partir de 2^4; instruction 1 : doubler tous les éléments du set précédent, Instruction 2 : extraire tous les i = (p-1)/3 du set précédent) Ce qui donne : 16--->32, 5---->64, 10---->128, 20, 21, 3----> 256, 40, 42, 6---->512, 80, 84, 12, 85, 13---->1024, 160, 168, 24, 170, 26----> 2048, 320, 336, 48, 340, 52, 341, 53---->...... chaque ---> correspond à un set qui est associé à un incrément de x à partir de 4 (remarque qu'il n'y a pas toujours de i dans un set)
2) Cette liste donne des impairs et x qui est l'exposant de la puissance de 2 du set où on les a trouvés :
3) x - 3 = nombre d'étapes paires et impaires d'une suite standard (non comp) mais que l'on arrête à 16 (impair de départ inclus et 16 inclus)
4) On peut maintenant extraire e, le nombre d'étapes impaires de la suite, en calculant : e= (x-log2(i))/log2(6) arrondi à l'entier le plus proche
5) on a maintenant une bdd avec i, x et e. Avec un calcul jusqu'à 2^34, la bdd comporte 1878 impairs. Il suffit alors d'utiliser une fonction comme min.si.ens (Excel) qui permet de trouver dans la bdd le plus petit x pour un e donné. Puis de faire un autre min.si.ens pour trouver par rapport à ce couple (e,x) quel est le plus petit i : Tu remarqueras que toute cette manip est faite sans jamais calculer une seule suite de Collatz.
Bon ben, en tout cas bravo pour la performance ! Je pense que ça me prendra moins la tête si je reste avec ma bonne vieille base de données. Merci quand même !
@Wilfrid Ok. Je te joins la bdd calculée pour 2^34 contenant 1878 impairs i avec le n° d'apparition (SUE), h (arrondi de log2(i); e (nbr étapes impaires), x (nbr total étapes paires et impaires), i et log2(i) (séparateur ";") Regarde ce que tu peux faire avec.
S'il faut faire des recherches dans un fichier CSV ou quel que soit son format, c'est trop compliqué, d'autant plus que selon toi il existe un risque que le résultat ne soit pas le bon. Avec ma base de données c'est direct et il n'y a aucune erreur possible.
PMF a écrit : un script Python serait bienvenu au cas où...
Certes, mais on écrit un script seulement après avoir conçu un algorithme, et en l'état actuel des choses il n'en existe aucun.
Je ne suis pas sûr que tu t'en rendes vraiment compte, mais tu es ton pire ennemi. On te répète depuis 2 ou 3 ans que personne ne comprend de quoi tu parles, mais tu continues comme si tu n'avais rien entendu, comme si tu étais un malheureux incompris en proie à la bêtise universelle. Pourtant, ce qui précède montre que tu peux voir juste ; mais en l'absence de la capacité d'effectuer des calculs au lieu de faire des phrases, et avec une telle inaptitude à le transmettre, le résultat de tes recherches est condamné à rester dans l'oubli. C'est bien dommage.
On définit un cluster{e,x} comme l'ensemble des impairs (i) de valeur proche ayant le même nombre d'étapes impaires (e) et le même nombre total d'étapes paires et impaires (x)
x est calculable par rapport à e et i : $x=\lceil e\cdot \log_26+\log_2{i} \rceil$
Les minorant et majorant d'un cluster {e, x} sont dans l'intervalle : $\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$ On peut observer dans les données que le ratio minorant/majorant est >0.8
Il est inutile de calculer chaque suite de Collatz dans l'ordre arithmétique des impairs pour trouver les valeurs x et e, et déterminer les impairs de chaque cluster : un algorithme peut générer une suite d'impairs dont la propriété est que tout impair de cette liste trouve toutes les étapes impaires de sa suite en revenant vers le début de la liste.
Cet algorithme ne comprend que 2 instructions : En partant de 2^4 (set initial) 1) Doubler les valeurs du set précédent 2) extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
Chaque itération correspond à une valeur de x (l'exposant de la puissance de 2 est égale au nombre d'étapes paires et impaires) Tous les i du même set correspondent donc au même x : $[i, x] : [5, 5], [21, 7], [3, 7], [85, 9], [13, 9], [341, 11], [53, 11], [113, 12], [17, 12], [1365, 13], [213, 13], [227, 13], [35, 13], [453, 14], [69, 14], [75, 14], [11, 14], [5461, 15], [853, 15], [909, 15], [141, 15], [151, 15], [23, 15], [1813, 16], [277, 16], [301, 16], [45, 16], [7, 16], [21845, 17], [3413, 17], [3637, 17]$ Comme i et x sont connus, il est alors possible de calculer e $e=\large \lceil \frac {x - log2(i)} { log_26} \rceil$
En calculant jusqu'à une valeur 2^x, la liste comprend un ensemble d'impairs répartis dans des clusters {e,x}. Le plus grand impair de la liste est $\large \frac {2^x-1}{3}$ en prenant la plus grande valeur paire de x
Pour 2^41, la liste comprend 9634 impairs répartis en 230 clusters. Le cluster le plus peuplé est {7, 41} avec 438 impairs Le graphique ci-dessous montre 12 alignements diagonaux correspondant à e de 1 à 12 (en allant de gauche à droite). Pour e = 13, il n'existe qu'un seul cluster {13,41} situé tout en bas à droite. Le grand impair est $\large \frac {2^{40}-1}{3} = 366503875925$ dans le cluster {1, 41} (donc tout en haut à droite du graph)
PMF a écrit : On définit un cluster {e, x} comme l'ensemble des impairs (i) de valeur proche ayant le même nombre d'étapes impaires (e) et le même nombre total d'étapes paires et impaires (x)
i : ensemble des impairs ... Pour ma part je parlerais de l'ensemble des n0 qui partagent certaines propriétés d'une suite de Collatz, comme la longueur et le nombre de termes impairs.
e : le nombre d'étapes impaires ... Comment le calcule-t-on ? Tient-on compte de n0 (ou i ) et de 1 ?
x : le nombre d'étapes paires et impaires ... J'appelle ça la longueur de la suite. Tient-elle compte de l'ensemble de ses termes, ou exclut-elle le premier ?
Une fois qu'on se sera compris sur les définitions, on pourra passer à la suite.
1) On peut effectivement nommer n0 le premier impair i d'une suite de Collatz. Ce n'est donc pas un impair ordinaire mais un impair que l'on choisit pour ses valeurs x et e, relatives à la suite de Collatz.
2) pour e : on ne tient pas compte de 1 pour la raison que nous sommes dans l'ensemble des n0 générés à partir de 2^4 (le plus petit i est 3). Exemple : 5 à une étape (lui-même. 3 a 2 étapes lui-même et 5. 17 a 3 étapes lui-même, 13 et 5, etc...
3) Oui x correspond à la longueur de la suite en partant du premier impair mais sans tenir compte de 1. Mais il est aussi l'exposant de 2^x . Dans toute suite de Collatz, 2^4 est toujours à x-3 termes du premier (que l'on compte comme 1er terme).
e : nombre d'étapes impaires, égal à T + 1 puisque T ne prend en compte ni n0 ni 1 alors que e tient compte de n0.
x : longueur de la suite, qui constitue un sérieux problème. La suite de 5 étant en effet 5, 16, 8, 4, 2, 1, si on ne tient pas compte de 1 il y a deux possibilités : 1) on considère que la suite s'arrête à 2, et donc sa longueur est 5 ; 2) comme c'est idiot, on s'arrête à 5, et la longueur de la suite est 1. Mais on peut ajouter 3) la longueur de la suite est 6 - 1 = 5 si on ne tient pas compte du 1, c'est-à-dire L - 1, où L est d'après moi la longueur totale de la suite.
Tout ceci témoigne de ton affection pour la complexité
e : cette manière de compter e avait été validée par @Collag3n il y a longtemps.
x : n'oublie pas que j'utilise x comme l'exposant (2^x) quand la liste des étapes impaires est calculée via l'algorithme. De ce fait, pour rappel on a en partant de 2^4 : x= 5 pour i (5) x = 7 pour i (21, 3) x = 9 pour i (85, 13) x = 11 pour i (341, 53) x = 12 pour i (113, 17) x = 13 pour i( 1365, 213, 227, 35) Mais je préfère utiliser x que dire "tdv" parce que je ne considère que les n0 (ou i) >1, et comme l'algorithme démarre à 2^4, quelque part c'est logique que tout se finit à 2^4.
Cette liste d'impairs $5, 21, 3, 85, 13, 341, 53, 113, 17, 1365, 213, 227, 35, 453, 69, 75, 11, 5461, 853, 909, 141, 151, 23, 1813, 277, 301, 45, 7$ est une compression, ou un cumul, de toutes les étapes impaires de toutes les suites des impairs contenus dans cette liste. Et dans le bon ordre !
Prend l'exemple de la suite de Collatz de 7 : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 On est bien d'accord qu'on trouve bien dans la liste 7, 11, 17, 13 et 5 en allant de gauche à droite.
Si la liste était infinie, elle contiendrait dans le bon ordre toutes les étapes impaires des suites de n'importe quel i >1
PMF a écrit : cette manière de compter e avait été validée par Collag3n il y a longtemps.
Ça ne signifie pas pour autant qu'elle a du sens. La longueur d'une suite correspond au nombre total de ses termes, et à rien d'autre. C'est comme si tu remplaçais ses termes par autant de centimètres : le dernier compte tout autant que les autres.
Si la liste était infinie, elle contiendrait dans le bon ordre toutes les étapes impaires des suites de n'importe quel i >1
Pas du tout ! Que fais-tu de l'infinité des suites qui ne font que passer par 7, 11, 17, 13, 5 ? Et de l'infinité de celles qui passent par 85 et non par 5 ? Il ne peut pas exister une suite de longueur infinie, mais une infinité de suites de longueur finie.
Je viens de me rendre compte que je me suis engagé dans la mauvaise voie en essayant de faire le parallèle entre ta méthode et la mienne. En fait, peu importe que la suite soit standard ou compressée, que le terme initial se nomme i ou n0 ; ce qui compte c'est la suite des valeurs minimales de n0 dont j'ai parlé plus haut. C'est la manière de la calculer sur laquelle je dois me concentrer.
PMF a écrit : Cet algorithme ne comprend que 2 instructions : En partant de 2^4 (set initial) 1) Doubler les valeurs du set précédent 2) extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
On part donc de 16, on multiplie par 2 à chaque itération, on regarde si le résultat est une puissance paire de 2. Si oui, on fait
$i=\dfrac{2^u-1}{3}$ avec $u$ pair, ce qui donnera $i$ entier impair.
On peut obtenir le même résultat de deux manières différentes :
On part de $u=2$ puis on calcule $i=\frac{2^{u+2}-1}{3}$ autant de fois qu'on veut.
On part de $i=1$ puis on calcule $i=4 \, i+1$ autant de fois qu'on veut.
Dans les deux cas on obtiendra la liste des prédécesseurs impairs de 1 : [1,] 5, 21, 85, 341, 1365, 5461, 21845, 87381, ...
l'exposant de la puissance de 2 est égal au nombre d'étapes paires et impaires
@Wilfrid Pour répondre à tes 3 derniers posts, laisse-moi te présenter LUC et LUCIE.
LUC pour Liste Universelle de Collatz est une liste de pairs et d'impairs produit par un algorithme ayant 2 instructions : En partant de 2^4 (set initial) 1) Doubler les valeurs du set précédent 2) extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
Ce qui donne en allant jusqu'à 2^11 LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13, 1024, 160, 168, 24, 170, 26, 2048, 320, 336, 48, 340, 52, 341, 53. On remarque que chaque set commence par un 2^x suivi d'une série paire, puis d'une série impaire (s'il y en a).
Prenons par exemple la suite de Collatz de 336 en la stoppant à 16 : 336,168, 84, 42, 21, 64, 32, 16 Tous les termes de cette suite sont dans LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13, 1024, 160, 168, 24, 170, 26, 2048, 320, 336, 48, 340, 52, 341, 53. En lisant de droite à gauche, toute la suite de 336 est dans le même ordre.
LUCIE pour Liste Universelle de Collatz réduite aux Etapes Impaires (on devrait dire LUCEI mais LUCIE c'est plus joli) On extrait LUCIE de LUC en ne gardant que les impairs, et en conservant strictement le même ordre : LUCIE : 5, 21, 3, 85, 13, 341, 53
Prenons par exemple la suite de Collatz de 53 en la stoppant à 16 : 53, 160, 80, 40, 20, 10, 5, 16 Tous les termes impairs de cette suite sont dans LUCIE : LUCIE : 5, 21, 3, 85, 13, 341, 53
Aussi longue soit LUCIE, c'est toujours le même principe : n'importe quel impair de LUCIE trouve dans la liste toutes les étapes impaires de sa suite de Collatz (sauf 1) en revenant vers le début.
Même en le voulant on arriverait difficilement à faire plus obscur.
extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
Il serait bon de commencer par définir ce qu'est un set (ensemble) et ce qu'est p. Comme je le disais précédemment, la formule que tu utilises indique que p est une puissance paire de 2, soit à partir de 16 : $2^4,2^6,2^8,...$
Ce qui donne en allant jusqu'à 2^11 LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, ...
Pourquoi 5, égal à $(2^4-1)/3$, se trouve-t-il après 32 ? Pourquoi 10 se trouve-t-il après 64 alors que $(2^6-1)/3=21$, lequel se retrouve entre $2^7$ et $2^8$. En quoi la phrase "extraire tous les impairs possibles" justifie-t-elle cette disposition ? Quelle information manque-t-il ? Je serais tenté de m'exclamer "c'est quoi ce bordel" !
Ci-joint un excel qui permet de vérifier que LUCIE (1878 impairs pour 2^34) contient toutes les étapes impaires des suites de Collatz de n'importe quel impair de cette liste
Mode d'emploi Aller dans l'onglet TESTER_LUCIE Appuyer sur la touche F9. Excel génère alors position aléatoire entre 1 et 1878 et la suite de Collatz de l'impair correspondant s'affiche en C3 et est calculée en colonne C. Pour chaque étape impaire de la suite, la position dans LUCIE est identifiée en colonne E.
Si @kioups cherche un nombre particulier (à condition qu'il soit bien dans LUCIE) Entrer ce nombre en cellule C3 (cellule en jaune) Regarder les positions en colonne E et vérifier tel St Thomas qu'ils sont bien à cette position dans l'onglet LUCIE
@lourrran Donc tu as compris le principe de LUC et LUCIE et tu pourrais l'expliquer à @Wilfrid Et éventuellement dire à @kioups que tous les impairs de LUCIE pour 2^34 sont corrects. À part cela, as-tu compris l'intérêt de LUCIE ?
Plutôt que LUCIE, tu aurais pu choisir comme acronyme COLUCHE ou DEBBOUZE, parce qu'on est plus dans le registre du comique que de l'origine de l'humanité. L'intérêt de LUCIE, j'ai compris, c'est de t'occuper. Pendant que tu fais ça, tu ne fais pas d'autres bêtises. Mais faire ça en public, est-ce nécessaire ?
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Finalement, tout le baratin qui s'est échangé depuis cette date a été une perte de temps. Il faut maintenant écrire l'algorithme qui permet de construire l'équivalent de ce tableau, et en extraire les valeurs impaires. Ça fait un moment que j'y réfléchis...
def tableauPMF(n, maxRangees):
tableau = [[n]]
for i in range(1, maxRangees):
nouvRangee = [x * 2 for x in tableau[i - 1]]
for x in tableau[i - 1]:
if (x - 1) % 3 == 0:
p = (x - 1) // 3
nouvRangee.append(p)
# if p not in nouvRangee: On vérifie si p ne figure pas déjà dans nouvRangee,
# nouvRangee.append(p) ce qui semble inutile mais peut servir le cas échéant
tableau.append(nouvRangee)
return tableau
initVal = 16
maxRangees = 8
tableau = tableauPMF(initVal, maxRangees)
for rangee in tableau:
print(rangee)
L'étape suivante est l'extraction des nombres impairs de chaque ligne du tableau. Mais il y a un hic : le 9 sur la 8ème ligne. Il résulte du 28 de la ligne précédente, puisque (28-1)/3 = 9. Je ne comprends d'ailleurs pas d'où sort ce 28. Un bug se serait-il sournoisement glissé dans mon algo ?
Wilfrid a écrit : Je ne comprends d'ailleurs pas d'où sort ce 28
Il sort du 85 de la ligne précédente, puisque (85 - 1)/3 = 28. La chaine 256 > 85 > 28 > 9 est inévitable, sauf si quelqu'un intervient de l'extérieur pour dire qu'il ne faut pas en tenir compte. Et ça c'est très embêtant.
Le bon test n'est pas : if (x - 1) % 3 == 0 Mais if (x - 4) % 6 == 0 Ou encore if x%6 == 4 On ne veut explorer cette branche que si ça nous emmène vers un impair.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Maintenant on a bien le même tableau que celui de PMF ci-dessus.
Voici une variante de l'algorithme qui affiche les nombres impairs du tableau en orange, pour plus de visibilité. A noter que le tableau sera composé de chaines de caractères numériques et non plus d'entiers. Ne pas l'utiliser pour l'extraction des entiers impairs :
def tableauPMF(n, maxRangees):
tableau = [[n]]
for i in range(1, maxRangees):
nouvRangee = [x * 2 for x in tableau[i - 1]]
for x in tableau[i - 1]:
if (x - 4) % 6 == 0:
p = (x - 1) // 3
nouvRangee.append(p)
# if p not in nouvRangee:
# nouvRangee.append(p)
# p = (x - 1) // 3
# if (x - 1) % 3 == 0 and p not in nouvRangee:
# nouvRangee.append(p)
tableau.append(nouvRangee)
return tableau
deb = '\033[33m' # Couleur ANSI orange, adaptée à un fond sombre
# deb = "\033[91m" # Couleur rouge, pour fond clair
fin = "\033[0m" # Reset de la couleur
initVal = 16
maxRangees = 8
tableau = tableauPMF(initVal, maxRangees)
for rangee in tableau:
rangee_coloree = " ".join([deb + str(element) + fin if element % 2 == 1 else str(element) for element in rangee])
print(rangee_coloree)
Cette version permet d'afficher ou non les nombres impairs en couleur en ne changeant que le booléen couleur, qui vaut True ou False (attention à l'initiale majuscule) :
def tableauPMF(n, maxRangees):
tableau = [[n]]
for i in range(1, maxRangees):
nouvRangee = [x * 2 for x in tableau[i - 1]]
for x in tableau[i - 1]:
# if (x - 1) % 3 == 0:
if (x - 4) % 6 == 0:
p = (x - 1) // 3
nouvRangee.append(p)
# if p not in nouvRangee:
# nouvRangee.append(p)
# p = (x - 1) // 3
# if (x - 1) % 3 == 0 and p not in nouvRangee:
# nouvRangee.append(p)
tableau.append(nouvRangee)
return tableau
deb = '\033[33m' # Couleur ANSI orange
# deb = "\033[91m" # Couleur rouge, si besoin
fin = "\033[0m" # Reset de la couleur
initVal = 16
maxRangees = 8
couleur = False
tableau = tableauPMF(initVal, maxRangees)
if couleur:
for rangee in tableau:
rangee_coloree = " ".join([deb + str(element) + fin if element %
2 == 1 else str(element) for element in rangee])
print(rangee_coloree)
else:
for rangee in tableau:
print(rangee)
Nouvelle et dernière version (?) de cet algorithme. Cette fois-ci il suffit de modifier un booléen pour que la liste des entiers impairs soit extraite du tableau (variable liste_impairs = True ou False). Avec un tableau de 12 rangées j'ai pu récupérer 23 nombres impairs (mais ce nombre augmente beaucoup plus rapidement que celui des rangées) :
Cependant, comme je l'expliquais dans ce message, il faudrait que PMF m'explique comment je peux les relier à la liste suivante, celle qui m'intéresse :
def tableauPMF(n, maxRangees):
tableau = [[n]]
for i in range(1, maxRangees):
nouvRangee = [x * 2 for x in tableau[i - 1]]
for x in tableau[i - 1]:
if (x - 4) % 6 == 0:
p = (x - 1) // 3
nouvRangee.append(p)
tableau.append(nouvRangee)
return tableau
deb = '\033[33m' # Couleur ANSI orange
# deb = "\033[91m" # Couleur rouge, si besoin
fin = "\033[0m" # Reset de la couleur
# Options
couleur = False
liste_impairs = True
# Paramètres
initVal = 16
maxRangees = 12
tableau = tableauPMF(initVal, maxRangees)
if liste_impairs:
if not couleur:
nombres_impairs = []
for rangee in tableau:
for nombre in rangee:
if nombre % 2 == 1:
nombres_impairs.append(nombre)
print(f"{len(nombres_impairs)} éléments") # Afficher le nombre d'éléments
print(nombres_impairs)
else:
print("Extraction de nombres colorés impossible")
else:
if couleur:
for rangee in tableau:
rangee_coloree = " ".join([deb + str(element) + fin if element % 2 == 1 else str(element) for element in rangee])
print(rangee_coloree)
else:
for rangee in tableau:
print(rangee)
Une précision importante : cette liste est celle des plus petits n0 dont le type est 2, 3, 4, 5, etc., le type étant le nombre de termes impairs diminué de 2 (n0 et 1). Par exemple, la suite compressée de 17 est 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, qui compte 2 termes impairs intermédiaires (13 et 5). Je précise que le type est bien entendu le même dans une suite standard et dans une suite compressée.
@Wilfrid Ta liste de n0 ne peut être obtenue qu'après avoir calculée LUCIE Il faut bien avoir les valeurs de x pour chaque i Après on peut déterminer e depuis i et x (formule déjà donnée) quand tu as des couples (e,x) pour chaque i, il faut chercher la plus petite valeur de x pour chaque e, puis dans cette sélection, la plus petite valeur de i et tu as ton n0 pour un (x, e) donné
Je joins le script Python modifié pour afficher les impairs regroupés par longueur de leur suite respective. Il y a maintenant 3 options :
# Options couleur = False # Afficher les nombres impairs en couleur liste_impairs = True # Afficher la liste des nombres impairs longueurs = True # Afficher la longueur de la suite de chaque nombre impair
Je suis sûr que pour me remercier tu vas mettre un point d'honneur à m'expliquer comment on passe de la suite 5, 21, 3, 85, 13, 341, 53, ... à la suite 17, 11, 7, 9, 25, 33, 43, ..., sans faire de phrases, sans prononcer le mot LUCIE, mais uniquement avec des formules.
Merci d'avance ! :-)
PS : au cas où, voici l'adresse d'un interpréteur Python (il n'affiche pas le texte en couleurs). Celui-ci affiche les couleurs.
@Wilfrid Le script fonctionne jusqu'à x = 34 (maxRangees = 31) et j'ai pu checker [vérifier ?] que les 1878 impairs sont corrects Je pense qu'il y a un souci après. En tout cas, bravo.
Ces listes sont très longues et peuvent dépasser la capacité d'affichage de la fenêtre de résultats, auquel cas tu peux trouver trois point de suspension quelque part entre deux rangées de nombres. Par exemple, avec initVal = 16 et maxRangees = 30, je trouve ces points de suspension entre le premier terme 268 435 456 d'une rangée et 1 073 741 824 au début de la rangée suivante, alors que c'est 536 870 912 qui aurait dû figurer (c'est-à-dire le double). Cette coupure est indépendante du script, c'est la fenêtre d'affichage qui la crée de manière à pouvoir afficher le résultat jusqu'à la fin, quitte à sacrifier le milieu. La solution est peut-être celle-ci :
Puis décommenter la ligne 62 (supprimer le # qui figure au début), c'est-à-dire remplacer
# Afficher sur une seule ligne : print(res_trie)
par
print(res_trie) # Afficher sur une seule ligne # for lg, n0_liste in res_trie.items(): # print(f"{deb+str(lg)+fin} {n0_liste}") # Variante sans couleur : print(f"{lg}: {n0_liste}")
C'est-à-dire que tu commentes le code qui affiche le résultat sur plusieurs lignes de manière à le désactiver.
PMF a écrit : Le script fonctionne jusqu'à x = 34 (maxRangees = 31)
Pas très parlante ta terminologie. Pourquoi ne remplaces-tu pas i par n0 et x par L ?
Je viens de tester initVal = 16 et maxRangees = 40. J'ai obtenu une liste de 15408 éléments, que je joins. On y trouve L (aka x) = 43. C'est d'après moi uniquement un problème d'affichage, la longueur de ces listes semblant croître exponentiellement.
J'ai modifié le script comme indiqué et vérifier que pour maxRangees = 31 les 1878 impairs étaient les bons Je note juste que la seule partie que j'importe se situe après <hide> Est-il possible de ne pas afficher toute la partie avant <hide> ?
Je viens de tester initVal = 16 et maxRangees = 40. J'ai obtenu une liste de 15408 éléments, que je joins. On y trouve L (aka x) = 43. C'est d'après moi uniquement un problème d'affichage, la longueur de ces listes semblant croître exponentiellement.
Dans le script que tu as joins, je ne peux pas transformer les données pour l'importation dans Excel. Le souci est qu'il n'y a pas de saut de ligne pour tout nouveau L (x pour moi)
Idéalement, il faudrait sortir comme ça:
5;5
7;3;21
9;13;85
11;53;341
12;17;113
13;35;213;227;1365
14;11;69;75;453
15;23;141;151;853;909;5461
16;7;45;277;301;1813
17;15;93;565;605;3413;3637;21845
Comme le premier terme de chaque ligne est L (aka x), on n'a pas besoin de lui donner une expression particulière Par exemple 15: [23, 141, 151, 853, 909, 5461] se remplace par 15;23;141;151;853;909;5461 et dans Excel la première colonne est x (L) et toutes les autres colonnes contiennent des i (n0) Chaque nouvelle ligne est un nouveau x...
Je reviens vers toi par rapport aux minorant et majorant d'un cluster $\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$
Lorsque que l'on calcule tous les descendants impairs i à partir de 16 jusqu'à une certaine valeur x (longueur), on obtient une liste comme ici pour x <=17:
(Un script Python est en cours de conception par @Wilfrid pour essayer d'atteindre des valeurs x plus grandes que le vba que j'ai utilisé jusqu'ici)
il est alors possible de calculer e, le nombre d'étapes impaires : $e=\lfloor \frac{x-log_2(i)}{log_26} \rfloor$ (corrigé)
On a alors les clusters {e,x} qui correspondent à tous les i de la liste.
Quelque soit la valeur de x atteinte, cette liste contient toujours des valeurs e de 1 à n. Pour e = 1, on a $\text{i=}\frac{2^{x-1}-1}{3}$ pour toutes les valeurs impaires de x>=5 : i (5, 21, 85, 341, 1365...)
Je pars de l'hypothèse suivante : il existe toujours une liste d'impairs associée à une valeur de x pour trouver tous les i tel que : $\frac{2^{x-1}-1}{3} <= i < \frac{2^{x+1}-1}{3}$ avec x impair >=5
Exemple pour x = 5, cela revient à 5 <= i < 21, soit 5, 7, 9, 11, 13, 15, 17, 19 que l'on trouve dans les clusters :
Donc tous les clusters donc les minorants et majorants sont dans cet intervalle vont fournir tous les i de 5 à 19.
On peut dire qu'il suffit de calculer la liste jusqu'à x = 20, pour remplir tout l'intervalle 5 <= i < 21
Evidemment il va vite falloir calculer de très longues listes car pour l'ntervalle suivant 21 <= i < 85, il faudrait aller à x = 115 et e = 42
Est-ce démontrable à ton avis de dire que tout intervalle $\frac{2^{x-1}-1}{3} <= i < \frac{2^{x+1}-1}{3}$ avec x impair >=5 sera toujours rempli pour une certaine valeur de x ?
C'est $e=\Big\lfloor \dfrac{x-\log_2(i)}{\log_26}\Big \rfloor$ (voir mon premier post d'il y a 3 ans).
Par "rempli pour une certaine valeur de $x$" tu veux dire : y a-t-il un $x$ maximum pour lequel l'intervalle est complet ?
La réponse est oui SI tous les nombres ont un TDV fini (pas de suite divergente). Ce sera le plus grand TDV trouvé dans l'intervalle (e.g. 73 donne 115).
Est-ce démontrable ? On l'espère, mais celui qui y arrive deviendra célèbre pour avoir résolu un des 2 points clés de Syracuse (divergence et cycles).
Nous avons donc toutes les valeurs deede 1 à 52 auxquelles sont associées 77 valeurs dexentre 9 et 143.
Le graphique ci-dessous montre les valeurs de i (points bleu) et l'intervalle minorant-majorant de chaque cluster (barres orange)
Si le graphique montre bien que $\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$ la position exacte de chaque i entre le minorant et le majorant est plus mystèrieuse : 1) Ils sont plutôt positionnés vers le majorant que le minorant. 2) les i ont tendance a être rapprochés s'il y a plusieurs impairs dans le même cluster. 3) certains alignements de i sont perceptibles (l'ordonnée montre le rang des clusters classés dans l'ordre de la liste ci-dessus)
A ma connaissance, on n'a rien qui explique 1) la position précise des impairs dans l'intervalle minorant-majorant, 2) le nombre d'impairs dans le cluster 3) pourquoi les impairs "se collent" quand ils sont dans le même cluster.
Qu'en dis-tu ?
En pièce jointe les données des 77 clusters de cet intervalle
Tu as le classique $1=\frac{3^e}{2^{x-e}}i+\frac{\delta}{2^{x-e}}$ avec $\delta$ le cumul des "+1"
Ce cumul est souvent assez petit par rapport à $3^ei$, ce qui fait que $1\sim \frac{3^e}{2^{x-e}}i$, donc $i$ est plus souvent proche $\frac{2^{x-e}}{3^e}$
Réponses
là il faut que tu m'expliques un peu plus.
Les 30 premières entrées de la base de données sont
n0tmin = {2: [17, 10], 3: [11, 11], 4: [7, 12], 5: [9, 14], 6: [25, 17], 7: [33, 19], 8: [43, 21], 9: [57, 23], 10: [39, 24], 11: [105, 27], 12: [135, 29], 13: [185, 31], 14: [123, 32], 15: [169, 34], 16: [219, 36], 17: [159, 37], 18: [379, 40], 19: [283, 41], 20: [377, 43], 21: [251, 44], 22: [167, 45], 23: [111, 46], 24: [297, 49], 25: [395, 51], 26: [263, 52], 27: [175, 53], 28: [233, 55], 29: [155, 56], 30: [103, 57], 31: [137, 59]}Je connais la suite jusque 427: [23183781049, 714]. Les éléments de ce dictionnaire Python sont composés d'une clé, T, et de ses deux valeurs associées, sous forme d'une liste : la plus petite valeur de n0 (impair) dont la suite compressée est de type T, et la longueur de celle-ci.
On peut oublier la clé T, qu'il suffit d'incrémenter à chaque nouveau calcul, ainsi que la longueur de chaque suite. Ce qu'il faudrait trouver c'est la règle ou formule qui définit la relation entre les termes successifs de la suite composée des valeurs de n0, c'est-à-dire 17, 11, 7, 9, 25, 33, 43, 57, 39, 105, 135, 185, 123, 169, 219, 159, 379, 283, 377, 251, etc.
Je ne peux pas croire que c'est le chaos total, qu'il n'existe aucune règle. Il existe nécessairement une méthode de calcul de la plus petite valeur de n0 dont la suite compressée est de type donné. Enfin c'est ce que je crois. Je pourrais poursuivre avec la recherche exhaustive et faire tourner un ordinateur pendant 10 ans pour arriver à T = 1000 (ou beaucoup moins avec un supercalculateur). Mais je pense que trouver une formule donnerait un nouvel éclairage à la structure dont j'ai parlé plus haut, et qui permet de faire les calculs dont j'ai donné quelques exemples.
Je rappelle toutefois que je parle de suites compressées, alors que toi tu t’intéresses aux suites standard. Or, ce dont il est question ici ne s'applique pas à ces suites, qui sont très différentes des suites compressées (il existe par exemple beaucoup moins de suites standard de longueur donnée que de suites compressées).
PS : pour arriver à 427 il m'a fallu calculer la suite compressée de chaque entier impair jusqu'à 23 183 781 049, ainsi que son type. La valeur du plus petit n0 de type 426 était 17 387 835 787. Il a donc fallu (23183781049 - 17387835787) / 2 = 2 897 972 631 itérations supplémentaires pour trouver le n0 suivant. Et cet écart ne fait que croître.
Merci pour toutes ces explications.
Cette liste de n0, 17, 11, 7, 9, 25, 33, 43, 57, 39, 105, 135, 185, 123, 169, 219, 159, 379, 283, 377, 251, correspond exactement à l'incrémentation de e à partir de 3. En ce cas, on trouve un n0 en cherchant la plus petite valeur de x pour un e donné. Par exemple, 17 est en e = 3 et x = 12, 11 en e = 4 et x = 14.
Je peux donc te proposer la liste suivante pour e <=125
Donc n0 est le plus petit impair d'un cluster dont la valeur e correspond au plus petit x possible.
Mais cela marche aussi pour e = 1 ou e = 2.
Pour e = 1, on a 5 avec x = 5
Pour e = 2, on a 3 avec x = 7
À partir de 1, on incrémente e pour trouver une valeur minimale de x pour une valeur minimale de i.
Par rapport à la formule de @Collag3n
$x=\lceil e \log_26 + \log_2i \rceil$
avec e = 3.
Pour i : 15, 17, 19, 21, 23, 25, x varie de 11.66 à 12.399 donc 6 candidats pour x = 12
Mais pourquoi choisir x = 12 et i = 17 ???
Le graphique montre en orange les n0 parmi les 1878 impairs pour x<=34
Comment veux-tu que je triche ?
Je reprend les explications :
D'abord et toujours on génère une liste d'impairs en partant de 2^4. Instruction 1 : doubler tous les éléments du set précédent Instruction 2 : extraire tous les i = (p-1)/3 du set précédent. Chaque set correspond à une puissance de 2 donc à un x. La liste des impairs que l'on obtient a donc un ordre qui lui est propre, et on peut associer chaque i à un x, et à un h = arrondi(log2(i)), ou simplement à log2(i).
Quand on affiche les données x, log2(i), on a le graphique de mon post précédent.
Il faut comprendre que la variable e, cad le nombre d"étapes impairs (i de départ inclus), est répresentée dans ce graphique par les alignements diagonaux, en partant de e = 1 à l'extrême gauche.
On peut donc constuire des clusters pour chaque i de coordonnées {h, e, x}
Tes n0 sont les plus petits impairs en bas de chaque diagonale. Donc pour les trouver, il suffit de partir de e = 1, puis de chercher quel est le plus petit impair ayant le plus petit x parmi les 1878 impairs générés pour x=34. On incrémente ensuite e jusqu'à 11 qui est la valeur max pour x = 34.
Si on veut produire une liste plus longue, c'est impossible pour moi de faire une liste avec x>34 (à cause du VBA.... script Python serait bienvenu au cas où...). Donc on fait autrement en générant les impairs dans l'ordre arithmétique et en calculant h, e, et x à partir des données des suites de Collatz (non compressées et que je tronque à 16). Je trouve mon x en ajoutant 3 au nombre total d'étapes paires ou impaires, i de départ et 16 inclus.
J'ai fait un calcul jusqu'à i = 100001 ce qui donne parmet d'atteindre h = 17. Cette liste permet de trouver tes n0 pour e <=125. Mais cette liste n'est pas la vraie liste que l'on obtient avec les 2 instructions. C'est une sorte d'ersatz qui suffit pour certaines choses mais pas pour tout.
voilà. c'est clair ?
Pas du tout. Je te demandais une méthode de calcul, un algorithme, pas un cours. Je t'ai souvent dit que tu ne savais pas t'expliquer, mais là c'est le pompon !
Imagines que tu expliques ta méthode à un enfant de 12 ans, et pas à quelqu'un qui a fait ça toute sa vie. Ça aidera certainement.
Réssayons.
1) on ne peut rien faire tant que la liste d'impairs provenant de l'algoritme n'est pas produite (à partir de 2^4; instruction 1 : doubler tous les éléments du set précédent, Instruction 2 : extraire tous les i = (p-1)/3 du set précédent)
Ce qui donne : 16--->32, 5---->64, 10---->128, 20, 21, 3----> 256, 40, 42, 6---->512, 80, 84, 12, 85, 13---->1024, 160, 168, 24, 170, 26----> 2048, 320, 336, 48, 340, 52, 341, 53---->......
chaque ---> correspond à un set qui est associé à un incrément de x à partir de 4 (remarque qu'il n'y a pas toujours de i dans un set)
2) Cette liste donne des impairs et x qui est l'exposant de la puissance de 2 du set où on les a trouvés :
3) x - 3 = nombre d'étapes paires et impaires d'une suite standard (non comp) mais que l'on arrête à 16 (impair de départ inclus et 16 inclus)
4) On peut maintenant extraire e, le nombre d'étapes impaires de la suite, en calculant : e= (x-log2(i))/log2(6) arrondi à l'entier le plus proche
5) on a maintenant une bdd avec i, x et e. Avec un calcul jusqu'à 2^34, la bdd comporte 1878 impairs. Il suffit alors d'utiliser une fonction comme min.si.ens (Excel) qui permet de trouver dans la bdd le plus petit x pour un e donné. Puis de faire un autre min.si.ens pour trouver par rapport à ce couple (e,x) quel est le plus petit i :
Tu remarqueras que toute cette manip est faite sans jamais calculer une seule suite de Collatz.
Je pense que ça me prendra moins la tête si je reste avec ma bonne vieille base de données. Merci quand même !
Ok. Je te joins la bdd calculée pour 2^34 contenant 1878 impairs i avec le n° d'apparition (SUE), h (arrondi de log2(i); e (nbr étapes impaires), x (nbr total étapes paires et impaires), i et log2(i)
(séparateur ";")
Regarde ce que tu peux faire avec.
S'il faut faire des recherches dans un fichier CSV ou quel que soit son format, c'est trop compliqué, d'autant plus que selon toi il existe un risque que le résultat ne soit pas le bon. Avec ma base de données c'est direct et il n'y a aucune erreur possible.
Certes, mais on écrit un script seulement après avoir conçu un algorithme, et en l'état actuel des choses il n'en existe aucun.
Je ne suis pas sûr que tu t'en rendes vraiment compte, mais tu es ton pire ennemi. On te répète depuis 2 ou 3 ans que personne ne comprend de quoi tu parles, mais tu continues comme si tu n'avais rien entendu, comme si tu étais un malheureux incompris en proie à la bêtise universelle. Pourtant, ce qui précède montre que tu peux voir juste ; mais en l'absence de la capacité d'effectuer des calculs au lieu de faire des phrases, et avec une telle inaptitude à le transmettre, le résultat de tes recherches est condamné à rester dans l'oubli. C'est bien dommage.
x est calculable par rapport à e et i :
$x=\lceil e\cdot \log_26+\log_2{i} \rceil$
Les minorant et majorant d'un cluster {e, x} sont dans l'intervalle :
$\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$
On peut observer dans les données que le ratio minorant/majorant est >0.8
Il est inutile de calculer chaque suite de Collatz dans l'ordre arithmétique des impairs pour trouver les valeurs x et e, et déterminer les impairs de chaque cluster : un algorithme peut générer une suite d'impairs dont la propriété est que tout impair de cette liste trouve toutes les étapes impaires de sa suite en revenant vers le début de la liste.
Cet algorithme ne comprend que 2 instructions :
En partant de 2^4 (set initial)
1) Doubler les valeurs du set précédent
2) extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
Chaque itération correspond à une valeur de x (l'exposant de la puissance de 2 est égale au nombre d'étapes paires et impaires)
Tous les i du même set correspondent donc au même x :
$[i, x] : [5, 5], [21, 7], [3, 7], [85, 9], [13, 9], [341, 11], [53, 11], [113, 12], [17, 12], [1365, 13], [213, 13], [227, 13], [35, 13], [453, 14], [69, 14], [75, 14], [11, 14], [5461, 15], [853, 15], [909, 15], [141, 15], [151, 15], [23, 15], [1813, 16], [277, 16], [301, 16], [45, 16], [7, 16], [21845, 17], [3413, 17], [3637, 17]$
Comme i et x sont connus, il est alors possible de calculer e
$e=\large \lceil \frac {x - log2(i)} { log_26} \rceil$
En calculant jusqu'à une valeur 2^x, la liste comprend un ensemble d'impairs répartis dans des clusters {e,x}.
Le plus grand impair de la liste est $\large \frac {2^x-1}{3}$ en prenant la plus grande valeur paire de x
Pour 2^41, la liste comprend 9634 impairs répartis en 230 clusters. Le cluster le plus peuplé est {7, 41} avec 438 impairs
Le graphique ci-dessous montre 12 alignements diagonaux correspondant à e de 1 à 12 (en allant de gauche à droite). Pour e = 13, il n'existe qu'un seul cluster {13,41} situé tout en bas à droite.
Le grand impair est $\large \frac {2^{40}-1}{3} = 366503875925$ dans le cluster {1, 41} (donc tout en haut à droite du graph)
i : ensemble des impairs ...
Pour ma part je parlerais de l'ensemble des n0 qui partagent certaines propriétés d'une suite de Collatz, comme la longueur et le nombre de termes impairs.
e : le nombre d'étapes impaires ...
Comment le calcule-t-on ? Tient-on compte de n0 (ou i ) et de 1 ?
x : le nombre d'étapes paires et impaires ...
J'appelle ça la longueur de la suite. Tient-elle compte de l'ensemble de ses termes, ou exclut-elle le premier ?
Une fois qu'on se sera compris sur les définitions, on pourra passer à la suite.
1) On peut effectivement nommer n0 le premier impair i d'une suite de Collatz. Ce n'est donc pas un impair ordinaire mais un impair que l'on choisit pour ses valeurs x et e, relatives à la suite de Collatz.
2) pour e : on ne tient pas compte de 1 pour la raison que nous sommes dans l'ensemble des n0 générés à partir de 2^4 (le plus petit i est 3).
Exemple : 5 à une étape (lui-même. 3 a 2 étapes lui-même et 5. 17 a 3 étapes lui-même, 13 et 5, etc...
3) Oui x correspond à la longueur de la suite en partant du premier impair mais sans tenir compte de 1. Mais il est aussi l'exposant de 2^x .
Dans toute suite de Collatz, 2^4 est toujours à x-3 termes du premier (que l'on compte comme 1er terme).
On a donc
e : nombre d'étapes impaires, égal à T + 1 puisque T ne prend en compte ni n0 ni 1 alors que e tient compte de n0.
x : longueur de la suite, qui constitue un sérieux problème. La suite de 5 étant en effet 5, 16, 8, 4, 2, 1, si on ne tient pas compte de 1 il y a deux possibilités : 1) on considère que la suite s'arrête à 2, et donc sa longueur est 5 ; 2) comme c'est idiot, on s'arrête à 5, et la longueur de la suite est 1. Mais on peut ajouter 3) la longueur de la suite est 6 - 1 = 5 si on ne tient pas compte du 1, c'est-à-dire L - 1, où L est d'après moi la longueur totale de la suite.
Tout ceci témoigne de ton affection pour la complexité
e : cette manière de compter e avait été validée par @Collag3n il y a longtemps.
x : n'oublie pas que j'utilise x comme l'exposant (2^x) quand la liste des étapes impaires est calculée via l'algorithme.
De ce fait, pour rappel on a en partant de 2^4 :
x= 5 pour i (5)
x = 7 pour i (21, 3)
x = 9 pour i (85, 13)
x = 11 pour i (341, 53)
x = 12 pour i (113, 17)
x = 13 pour i( 1365, 213, 227, 35)
Mais je préfère utiliser x que dire "tdv" parce que je ne considère que les n0 (ou i) >1, et comme l'algorithme démarre à 2^4, quelque part c'est logique que tout se finit à 2^4.
Cette liste d'impairs $5, 21, 3, 85, 13, 341, 53, 113, 17, 1365, 213, 227, 35, 453, 69, 75, 11, 5461, 853, 909, 141, 151, 23, 1813, 277, 301, 45, 7$ est une compression, ou un cumul, de toutes les étapes impaires de toutes les suites des impairs contenus dans cette liste. Et dans le bon ordre !
Prend l'exemple de la suite de Collatz de 7 : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
On est bien d'accord qu'on trouve bien dans la liste 7, 11, 17, 13 et 5 en allant de gauche à droite.
Si la liste était infinie, elle contiendrait dans le bon ordre toutes les étapes impaires des suites de n'importe quel i >1
Ça ne signifie pas pour autant qu'elle a du sens. La longueur d'une suite correspond au nombre total de ses termes, et à rien d'autre. C'est comme si tu remplaçais ses termes par autant de centimètres : le dernier compte tout autant que les autres.
Pas du tout ! Que fais-tu de l'infinité des suites qui ne font que passer par 7, 11, 17, 13, 5 ? Et de l'infinité de celles qui passent par 85 et non par 5 ? Il ne peut pas exister une suite de longueur infinie, mais une infinité de suites de longueur finie.
On part donc de 16, on multiplie par 2 à chaque itération, on regarde si le résultat est une puissance paire de 2. Si oui, on fait
$i=\dfrac{2^u-1}{3}$ avec $u$ pair, ce qui donnera $i$ entier impair.
On peut obtenir le même résultat de deux manières différentes :
On part de $u=2$ puis on calcule $i=\frac{2^{u+2}-1}{3}$ autant de fois qu'on veut.
On part de $i=1$ puis on calcule $i=4 \, i+1$ autant de fois qu'on veut.
Dans les deux cas on obtiendra la liste des prédécesseurs impairs de 1 : [1,] 5, 21, 85, 341, 1365, 5461, 21845, 87381, ...
Exemples avec $2^4,2^6,2^8$ : 16, 8, 4, 2, 1 || 64, 32, 16, 8, 4, 2, 1 || 256, 128, 64, 32, 16, 8, 4, 2, 1
Et ensuite, qu'est-ce qu'on fait ?
Pour répondre à tes 3 derniers posts, laisse-moi te présenter LUC et LUCIE.
LUC pour Liste Universelle de Collatz est une liste de pairs et d'impairs produit par un algorithme ayant 2 instructions :
En partant de 2^4 (set initial)
1) Doubler les valeurs du set précédent
2) extraire tous les impairs possibles des valeurs paires du set précédent tel que i = (p-1)/3
Ce qui donne en allant jusqu'à 2^11
LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13, 1024, 160, 168, 24, 170, 26, 2048, 320, 336, 48, 340, 52, 341, 53.
On remarque que chaque set commence par un 2^x suivi d'une série paire, puis d'une série impaire (s'il y en a).
Prenons par exemple la suite de Collatz de 336 en la stoppant à 16 : 336, 168, 84, 42, 21, 64, 32, 16
Tous les termes de cette suite sont dans LUC :
16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13, 1024, 160, 168, 24, 170, 26, 2048, 320, 336, 48, 340, 52, 341, 53.
En lisant de droite à gauche, toute la suite de 336 est dans le même ordre.
LUCIE pour Liste Universelle de Collatz réduite aux Etapes Impaires (on devrait dire LUCEI mais LUCIE c'est plus joli)
On extrait LUCIE de LUC en ne gardant que les impairs, et en conservant strictement le même ordre :
LUCIE : 5, 21, 3, 85, 13, 341, 53
Prenons par exemple la suite de Collatz de 53 en la stoppant à 16 : 53, 160, 80, 40, 20, 10, 5, 16
Tous les termes impairs de cette suite sont dans LUCIE :
LUCIE : 5, 21, 3, 85, 13, 341, 53
Aussi longue soit LUCIE, c'est toujours le même principe : n'importe quel impair de LUCIE trouve dans la liste toutes les étapes impaires de sa suite de Collatz (sauf 1) en revenant vers le début.
Par exemple pour 2^22
LUCIE : 5, 21, 3, 85, 13, 341, 53, 113, 17, 1365, 213, 227, 35, 453, 69, 75, 11, 5461, 853, 909, 141, 151, 23, 1813, 277, 301, 45, 7, 21845, 3413, 3637, 565, 605, 93, 15, 7253, 1109, 1205, 181, 29, 7281, 1137, 201, 87381, 13653, 14549, 2261, 2421, 373, 61, 2417, 369, 401, 9, 14563, 2275, 403, 29013, 4437, 4821, 725, 117, 29125, 4549, 805, 4849, 753, 4835, 739, 803, 19, 349525, 54613, 58197, 9045, 9685, 1493, 245, 9669, 1477, 1605, 37, 58253, 9101, 1613, 241, 9699, 1507, 1611, 267, 116053, 17749, 19285, 2901, 469, 116501, 18197, 3221, 19397, 3013, 19341, 2957, 3213, 77, 497, 81, 19417, 3033, 537, 483, 3223, 535
Les impairs en gras montrent les étapes impaires de la suite de 81 : 81, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16.
Même en le voulant on arriverait difficilement à faire plus obscur.
Il serait bon de commencer par définir ce qu'est un set (ensemble) et ce qu'est p. Comme je le disais précédemment, la formule que tu utilises indique que p est une puissance paire de 2, soit à partir de 16 : $2^4,2^6,2^8,...$
Pourquoi 5, égal à $(2^4-1)/3$, se trouve-t-il après 32 ? Pourquoi 10 se trouve-t-il après 64 alors que $(2^6-1)/3=21$, lequel se retrouve entre $2^7$ et $2^8$. En quoi la phrase "extraire tous les impairs possibles" justifie-t-elle cette disposition ? Quelle information manque-t-il ? Je serais tenté de m'exclamer "c'est quoi ce bordel" !
"Et ensuite, qu'est-ce qu'on fait ?"
Ce que tu indiques ne permet de calculer que les i pour e = 1
Je te redonne donc ce que fait l'algorithme set par set
Set 2^4 :
On pose 16 comme point de départ
Set 2^5 :
Instruction 1 : 32
Instruction 2 : 5
LUC : 16, 32, 5
Set 2^6 :
Instruction 1 : 64, 10
Instruction 2 : nul
LUC : 16, 32, 5, 64, 10
Set 2^7 :
Instruction 1 : 128, 20
Instruction 2 : 21, 3
LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3
Set 2^8 :
Instruction 1 : 256, 40, 42, 6
Instruction 2 : nul
LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6
Set 2^9 :
Instruction 1 : 512, 80, 84, 12
Instruction 2 : 85, 13
LUC : 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13
Si on s'arrête là, on enlève les pairs et on obtient LUCIE : 5, 21, 3, 85, 13
Voici la liste jusqu'à 2^34 avec en gras toutes les étapes de i=39 qui a le plus grand nombre d'étapes impaires de la liste (e=11)
LUCIE : 5, 21, 3, 85, 13, 341, 53, 113, 17, 1365, 213, 227, 35, 453, 69, 75, 11, 5461, 853, 909, 141, 151, 23, 1813, 277, 301, 45, 7, 21845, 3413, 3637, 565, 605, 93, 15, 7253, 1109, 1205, 181, 29, 7281, 1137, 201, 87381, 13653, 14549, 2261, 2421, 373, 61, 2417, 369, 401, 9, 14563, 2275, 403, 29013, 4437, 4821, 725, 117, 29125, 4549, 805, 4849, 753, 4835, 739, 803, 19, 349525, 54613, 58197, 9045, 9685, 1493, 245, 9669, 1477, 1605, 37, 58253, 9101, 1613, 241, 9699, 1507, 1611, 267, 116053, 17749, 19285, 2901, 469, 116501, 18197, 3221, 19397, 3013, 19341, 2957, 3213, 77, 497, 81, 19417, 3033, 537, 483, 3223, 535, 1398101, 218453, 232789, 36181, 38741, 5973, 981, 38677, 5909, 6421, 149, 233013, 36405, 6453, 965, 38797, 6029, 6445, 1069, 38833, 6065, 1073, 6465, 985, 25, 995, 163, 38835, 6067, 1075, 464213, 70997, 77141, 11605, 1877, 466005, 72789, 12885, 77589, 12053, 77365, 11829, 12853, 309, 1989, 325, 77669, 12133, 2149, 1933, 12893, 2141, 466033, 72817, 12913, 1969, 49, 321, 2009, 77667, 12131, 2147, 12931, 1971, 51, 331, 5592405, 873813, 931157, 144725, 154965, 23893, 3925, 154709, 23637, 25685, 597, 932053, 145621, 25813, 3861, 155189, 24117, 25781, 4277, 155333, 24261, 4293, 25861, 3941, 101, 3981, 653, 155341, 24269, 4301, 154737, 23665, 25713, 625, 4017, 25889, 4297, 713, 932067, 145635, 25827, 3939, 99, 643, 4019, 4043, 715, 663, 1856853, 283989, 308565, 46421, 7509, 1864021, 291157, 51541, 310357, 48213, 309461, 47317, 51413, 1237, 7957, 1301, 310677, 48533, 8597, 7733, 51573, 8565, 1864133, 291269, 51653, 7877, 197, 1285, 8037, 310669, 48525, 8589, 51725, 7885, 205, 1325, 310385, 48241, 51569, 8561, 51729, 8593, 1425, 51777, 1313, 33, 217, 8089, 1433, 309475, 47331, 51427, 1251, 8035, 51779, 8595, 1427, 1339, 8087, 1431, 22369621, 3495253, 3724629, 578901, 619861, 95573, 15701, 618837, 94549, 102741, 2389, 3728213, 582485, 103253, 15445, 620757, 96469, 103125, 17109, 621333, 97045, 17173, 103445, 15765, 405, 15925, 2613, 621365, 97077, 17205, 618949, 94661, 102853, 2501, 16069, 103557, 17189, 2853, 3728269, 582541, 103309, 15757, 397, 2573, 16077, 16173, 2861, 2653, 15473, 103153, 17137, 433, 16177, 2865, 2577, 621377, 97089, 17217, 2625, 65, 17241, 441, 620771, 96483, 103139, 17123, 103459, 17187, 2851, 103555, 2627, 67, 435, 16179, 2867, 17259, 475, 2679, 2695, 7427413, 1135957, 1234261, 185685, 30037, 7456085, 1164629, 206165, 1241429, 192853, 1237845, 189269, 205653, 4949, 31829, 5205, 1242709, 194133, 34389, 30933, 206293, 34261, 7456533, 1165077, 206613, 31509, 789, 5141, 32149, 1242677, 194101, 34357, 206901, 31541, 821, 5301, 1241541, 192965, 206277, 34245, 206917, 34373, 5701, 207109, 5253, 133, 869, 32357, 5733, 1237901, 189325, 205709, 5005, 32141, 207117, 34381, 5709, 5357, 32349, 5725, 31857, 5233, 1242737, 194161, 34417, 34481, 207121, 31553, 833, 5729, 857, 953, 30947, 206307, 34275, 867, 32355, 5731, 5155, 1242755, 194179, 34435, 5251, 131, 34483, 883, 206923, 34379, 5707, 875, 955, 34519, 951, 5391, 89478485, 13981013, 14898517, 2315605, 2479445, 382293, 62805, 2475349, 378197, 410965, 9557, 14912853, 2329941, 413013, 61781, 2483029, 385877, 412501, 68437, 2485333, 388181, 68693, 413781, 63061, 1621, 63701, 10453, 2485461, 388309, 68821, 2475797, 378645, 411413, 10005, 64277, 414229, 68757, 11413, 14913077, 2330165, 413237, 63029, 1589, 10293, 64309, 64693, 11445, 10613, 61893, 412613, 68549, 1733, 64709, 11461, 10309, 2485509, 388357, 68869, 10501, 261, 68965, 1765, 2483085, 385933, 412557, 68493, 413837, 68749, 11405, 414221, 10509, 269, 1741, 64717, 11469, 69037, 1901, 10717, 10781, 2485361, 388209, 68721, 413809, 63089, 1649, 10609, 1713, 414225, 10513, 273, 64321, 11457, 289, 10785, 412633, 68569, 10713, 1785, 63715, 10467, 2485475, 388323, 68835, 68963, 414243, 63107, 1667, 11459, 1715, 1907, 10315, 414251, 43, 413847, 68759, 11415, 1751, 1911, 29709653, 4543829, 4937045, 742741, 120149, 29824341, 4658517, 824661, 4965717, 771413, 4951381, 757077, 822613, 19797, 127317, 20821, 4970837, 776533, 137557, 123733, 825173, 137045, 29826133, 4660309, 826453, 126037, 3157, 20565, 128597, 4970709, 776405, 137429, 827605, 126165, 3285, 21205, 4966165, 771861, 825109, 136981, 827669, 137493, 22805, 828437, 21013, 533, 3477, 129429, 22933, 4951605, 757301, 822837, 20021, 128565, 828469, 137525, 22837, 21429, 129397, 22901, 127429, 20933, 4970949, 776645, 137669, 137925, 828485, 126213, 3333, 22917, 3429, 3813, 123789, 825229, 137101, 3469, 129421, 22925, 20621, 4971021, 776717, 137741, 21005, 525, 137933, 3533, 827693, 137517, 22829, 3501, 3821, 138077, 3805, 21565, 29826161, 4660337, 826481, 126065, 3185, 20593, 128625, 129393, 22897, 21233, 825265, 137137, 21425, 4971025, 776721, 137745, 21009, 529, 3537, 137537, 22849, 577, 21569, 137945, 3801, 138073, 89, 633, 3593, 4970723, 776419, 137443, 827619, 126179, 3299, 21219, 3427, 828451, 21027, 547, 128643, 22915, 579, 21571, 825267, 137139, 21427, 3571, 828491, 22987, 21035, 555, 3819, 571, 635, 20631, 828503, 87, 22919, 583, 357913941, 55924053, 59594069, 9262421, 9917781, 1529173, 251221, 9901397, 1512789, 1643861, 38229, 59651413, 9319765, 1652053, 247125, 9932117, 1543509, 1650005, 273749, 9941333, 1552725, 274773, 1655125, 252245, 6485, 254805, 41813, 9941845, 1553237, 275285, 9903189, 1514581, 1645653, 40021, 257109, 1656917, 275029, 45653, 59652309, 9320661, 1652949, 252117, 6357, 41173, 257237, 258773, 45781, 42453, 247573, 1650453, 274197, 6933, 258837, 45845, 41237, 9942037, 1553429, 275477, 42005, 1045, 275861, 7061, 9932341, 1543733, 1650229, 273973, 1655349, 274997, 45621, 1656885, 42037, 1077, 6965, 258869, 45877, 276149, 7605, 42869, 43125, 9941445, 1552837, 274885, 1655237, 252357, 6597, 42437, 6853, 1656901, 42053, 1093, 257285, 45829, 1157, 43141, 1650533, 274277, 42853, 7141, 254861, 41869, 9941901, 1553293, 275341, 275853, 1656973, 252429, 6669, 45837, 6861, 7629, 41261, 1657005, 173, 1655389, 275037, 45661, 7005, 7645, 9903217, 1514609, 1645681, 40049, 257137, 1656945, 275057, 45681, 42865, 258801, 45809, 275889, 7601, 276145, 177, 252433, 6673, 45841, 7633, 6977, 258881, 45889, 276161, 7641, 6873, 258905, 45913, 7001, 45977, 1177, 275897, 7609, 1273, 46025, 59652323, 9320675, 1652963, 252131, 6371, 41187, 257251, 258787, 45795, 42467, 1650531, 274275, 42851, 9942051, 1553443, 275491, 42019, 1059, 7075, 275075, 45699, 1155, 43139, 275891, 7603, 276147, 179, 1267, 7187, 1656907, 42059, 1099, 1656983, 45975, 42071, 1111, 7639, 1143, 1271, 276167, 45839, 1167, 118838613, 18175317, 19748181, 2970965, 480597, 119297365, 18634069, 3298645, 19862869, 3085653, 19805525, 3028309, 3290453, 79189, 509269, 83285, 19883349, 3106133, 550229, 494933, 3300693, 548181, 119304533, 18641237, 3305813, 504149, 12629, 82261, 514389, 19882837, 3105621, 549717, 3310421, 504661, 13141, 84821, 19864661, 3087445, 3300437, 547925, 3310677, 549973, 91221, 3313749, 84053, 2133, 13909, 517717, 91733, 19806421, 3029205, 3291349, 80085, 514261, 3313877, 550101, 91349, 85717, 517589, 91605, 509717, 83733, 19883797, 3106581, 550677, 551701, 3313941, 504853, 13333, 91669, 13717, 15253, 495157, 3300917, 548405, 13877, 517685, 91701, 82485, 19884085, 3106869, 550965, 84021, 2101, 551733, 14133, 3310773, 550069, 91317, 14005, 15285, 552309, 15221, 86261, 119304645, 18641349, 3305925, 504261, 12741, 82373, 514501, 517573, 91589, 84933, 3301061, 548549, 85701, 19884101, 3106885, 550981, 84037, 2117, 14149, 550149, 91397, 2309, 86277, 551781, 15205, 552293, 357, 2533, 14373, 19882893, 3105677, 549773, 3310477, 504717, 13197, 84877, 13709, 3313805, 84109, 2189, 514573, 91661, 2317, 86285, 3301069, 548557, 85709, 14285, 3313965, 91949, 84141, 2221, 15277, 2285, 2541, 82525, 3314013, 349, 91677, 2333, 19864689, 3087473, 3300465, 547953, 3310705, 550001, 91249, 3313777, 84081, 2161, 13937, 517745, 91761, 552305, 15217, 85745, 86257, 15281, 13745, 517809, 91825, 14001, 91953, 2353, 514577, 91665, 2321, 86289, 92049, 14289, 551745, 14145, 14017, 85761, 385, 550177, 91425, 84953, 13753, 57, 19806435, 3029219, 3291363, 80099, 514275, 3313891, 550115, 91363, 85731, 517603, 91619, 551779, 15203, 552291, 355, 504867, 13347, 91683, 15267, 13955, 517763, 91779, 552323, 15283, 13747, 517811, 91827, 14003, 91955, 2355, 551795, 15219, 2547, 92051, 19884107, 3106891, 550987, 84043, 2123, 14155, 14283, 91691, 14379, 91963, 59, 2395, 3313815, 84119, 2199, 552327, 14023, 423, 552335, 15279, 1431655765, 223696213, 238376277, 37049685, 39671125, 6116693, 1004885, 39605589, 6051157, 6575445, 152917, 238605653, 37279061, 6608213, 988501, 39728469, 6174037, 6600021, 1094997, 39765333, 6210901, 1099093, 6620501, 1008981, 25941, 1019221, 167253, 39767381, 6212949, 1101141, 39612757, 6058325, 6582613, 160085, 1028437, 6627669, 1100117, 182613, 238609237, 37282645, 6611797, 1008469, 25429, 164693, 1028949, 1035093, 183125, 169813, 990293, 6601813, 1096789, 27733, 1035349, 183381, 164949, 39768149, 6213717, 1101909, 168021, 4181, 1103445, 28245, 39729365, 6174933, 6600917, 1095893, 6621397, 1099989, 182485, 6627541, 168149, 4309, 27861, 1035477, 183509, 1104597, 30421, 171477, 172501, 39765781, 6211349, 1099541, 6620949, 1009429, 26389, 169749, 27413, 6627605, 168213, 4373, 1029141, 183317, 4629, 172565, 6602133, 1097109, 171413, 28565, 1019445, 167477, 39767605, 6213173, 1101365, 1103413, 6627893, 1009717, 26677, 183349, 27445, 30517, 165045, 6628021, 693, 6621557, 1100149, 182645, 28021, 30581, 39612869, 6058437, 6582725, 160197, 1028549, 6627781, 1100229, 182725, 171461, 1035205, 183237, 1103557, 30405, 1104581, 709, 1009733, 26693, 183365, 30533, 27909, 1035525, 183557, 1104645, 30565, 27493, 1035621, 183653, 28005, 183909, 4709, 1103589, 30437, 5093, 184101, 238609293, 37282701, 6611853, 1008525, 25485, 164749, 1029005, 1035149, 183181, 169869, 6602125, 1097101, 171405, 39768205, 6213773, 1101965, 168077, 4237, 28301, 1100301, 182797, 4621, 172557, 1103565, 30413, 1104589, 717, 5069, 28749, 6627629, 168237, 4397, 6627933, 183901, 168285, 4445, 30557, 4573, 5085, 1104669, 183357, 4669, 990321, 6601841, 1096817, 27761, 1035377, 183409, 164977, 39768177, 6213745, 1101937, 168049, 4209, 1103473, 28273, 6621553, 1100145, 182641, 28017, 30577, 1104625, 30449, 172529, 169905, 1100305, 182801, 4625, 172561, 5073, 28753, 27457, 30529, 1100353, 182849, 6628033, 705, 30465, 769, 184097, 1035225, 183257, 4569, 1104601, 729, 30553, 28761, 28569, 4761, 30649, 761, 777, 39729379, 6174947, 6600931, 1095907, 6621411, 1100003, 182499, 6627555, 168163, 4323, 27875, 1035491, 183523, 1104611, 30435, 171491, 172515, 30563, 27491, 1035619, 183651, 28003, 183907, 4707, 1029155, 183331, 4643, 172579, 184099, 28579, 1103491, 28291, 28035, 171523, 771, 1100355, 182851, 169907, 27507, 115, 1009739, 26699, 183371, 30539, 5067, 4651, 172587, 184107, 172603, 4667, 30651, 183931, 30683, 39768215, 6213783, 1101975, 168087, 4247, 28311, 28567, 183383, 28759, 183927, 119, 4791, 28039, 1104655, 28047, 847, 184111, 30559, 475354453, 72701269, 78992725, 11883861, 1922389, 477189461, 74536277, 13194581, 79451477, 12342613, 79222101, 12113237, 13161813, 316757, 2037077, 333141, 79533397, 12424533, 2200917, 1979733, 13202773, 2192725, 477218133, 74564949, 13223253, 2016597, 50517, 329045, 2057557, 79531349, 12422485, 2198869, 13241685, 2018645, 52565, 339285, 79458645, 12349781, 13201749, 2191701, 13242709, 2199893, 364885, 13254997, 336213, 8533, 55637, 2070869, 366933, 79225685, 12116821, 13165397, 320341, 2057045, 13255509, 2200405, 365397, 342869, 2070357, 366421, 2038869, 334933, 79535189, 12426325, 2202709, 2206805, 13255765, 2019413, 53333, 366677, 54869, 61013, 1980629, 13203669, 2193621, 55509, 2070741, 366805, 329941, 79536341, 12427477, 2203861, 336085, 8405, 2206933, 56533, 13243093, 2200277, 365269, 56021, 61141, 2209237, 60885, 345045, 477218581, 74565397, 13223701, 2017045, 50965, 329493, 2058005, 2070293, 366357, 339733, 13204245, 2194197, 342805, 79536405, 12427541, 2203925, 336149, 8469, 56597, 2200597, 365589, 9237, 345109, 2207125, 60821, 2209173, 1429, 10133, 57493, 79531573, 12422709, 2199093, 13241909, 2018869, 52789, 339509, 54837, 13255221, 336437, 8757, 2058293, 366645, 9269, 345141, 13204277, 2194229, 342837, 57141, 13255861, 367797, 336565, 8885, 61109, 9141, 10165, 330101, 13256053, 1397, 366709, 9333, 79458757, 12349893, 13201861, 2191813, 13242821, 2200005, 364997, 13255109, 336325, 8645, 55749, 2070981, 367045, 2209221, 60869, 342981, 345029, 61125, 54981, 2071237, 367301, 56005, 367813, 9413, 2058309, 366661, 9285, 345157, 368197, 57157, 2206981, 56581, 56069, 343045, 1541, 2200709, 365701, 339813, 55013, 229, 79225741, 12116877, 13165453, 320397, 2057101, 13255565, 2200461, 365453, 342925, 2070413, 366477, 2207117, 60813, 2209165, 1421, 2019469, 53389, 366733, 61069, 55821, 2071053, 367117, 2209293, 61133, 54989, 2071245, 367309, 56013, 367821, 9421, 2207181, 60877, 10189, 368205, 79536429, 12427565, 2203949, 336173, 8493, 56621, 57133, 366765, 57517, 367853, 237, 9581, 13255261, 336477, 8797, 2209309, 56093, 1693, 2209341, 61117, 2038897, 334961, 79535217, 12426353, 2202737, 2206833, 13255793, 2019441, 53361, 366705, 54897, 61041, 330097, 13256049, 1393, 13243121, 2200305, 365297, 56049, 61169, 2070449, 366513, 9137, 2209201, 1457, 61105, 57521, 57137, 9521, 55825, 2071057, 367121, 2209297, 2207185, 60881, 10193, 13204289, 2194241, 342849, 57153, 368193, 336577, 8897, 61121, 10177, 61185, 61217, 1569, 10145, 1697, 343001, 345049, 2071257, 367321, 56025, 9433, 10137, 1689, 2209209, 1465, 1481, 10185, 1980643, 13203683, 2193635, 55523, 2070755, 366819, 329955, 79536355, 12427491, 2203875, 336099, 8419, 2206947, 56547, 13243107, 2200291, 365283, 56035, 61155, 2209251, 60899, 345059, 339811, 2200611, 365603, 9251, 345123, 10147, 57507, 54915, 61059, 2200707, 365699, 13256067, 1411, 60931, 1539, 368195, 2070451, 366515, 9139, 2209203, 1459, 61107, 57523, 57139, 9523, 61299, 1523, 1555, 2058315, 366667, 9291, 345163, 368203, 57163, 10187, 9163, 343051, 1547, 56635, 2019479, 53399, 366743, 61079, 10135, 9303, 345175, 368215, 345207, 9335, 61303, 367863, 61367, 13256071, 1415, 61127, 39, 56079, 368223
Génération 0 : 16
Génération 1 : descendants pairs : 32 ; descendants impairs : 5
Génération 2 ; descendants pairs : 64, 10 ; descendants impairs : aucun
Génération 3 ; descendants pairs : 128,20 ; descendants impairs : 21,3
Génération 4 ; etc etc
Ci-joint un excel qui permet de vérifier que LUCIE (1878 impairs pour 2^34) contient toutes les étapes impaires des suites de Collatz de n'importe quel impair de cette liste
Mode d'emploi
Aller dans l'onglet TESTER_LUCIE
Appuyer sur la touche F9.
Excel génère alors position aléatoire entre 1 et 1878 et la suite de Collatz de l'impair correspondant s'affiche en C3 et est calculée en colonne C.
Pour chaque étape impaire de la suite, la position dans LUCIE est identifiée en colonne E.
Si @kioups cherche un nombre particulier (à condition qu'il soit bien dans LUCIE)
Entrer ce nombre en cellule C3 (cellule en jaune)
Regarder les positions en colonne E et vérifier tel St Thomas qu'ils sont bien à cette position dans l'onglet LUCIE
Donc tu as compris le principe de LUC et LUCIE et tu pourrais l'expliquer à @Wilfrid
Et éventuellement dire à @kioups que tous les impairs de LUCIE pour 2^34 sont corrects.
À part cela, as-tu compris l'intérêt de LUCIE ?
L'intérêt de LUCIE, j'ai compris, c'est de t'occuper. Pendant que tu fais ça, tu ne fais pas d'autres bêtises. Mais faire ça en public, est-ce nécessaire ?
32, 5
64, 10
128, 20, 21, 3
256, 40, 42, 6
512, 80, 84, 12, 85, 13
1024, 160, 168, 24, 170, 26
2048, 320, 336, 48, 340, 52, 341, 53
Tadaaaa ! :-)
def tableauPMF(n, maxRangees): tableau = [[n]] for i in range(1, maxRangees): nouvRangee = [x * 2 for x in tableau[i - 1]] for x in tableau[i - 1]: if (x - 1) % 3 == 0: p = (x - 1) // 3 nouvRangee.append(p) # if p not in nouvRangee: On vérifie si p ne figure pas déjà dans nouvRangee, # nouvRangee.append(p) ce qui semble inutile mais peut servir le cas échéant tableau.append(nouvRangee) return tableau initVal = 16 maxRangees = 8 tableau = tableauPMF(initVal, maxRangees) for rangee in tableau: print(rangee)Résultat :
[16]
[32, 5]
[64, 10]
[128, 20, 21, 3]
[256, 40, 42, 6]
[512, 80, 84, 12, 85, 13]
[1024, 160, 168, 24, 170, 26, 28, 4]
[2048, 320, 336, 48, 340, 52, 56, 8, 341, 53, 9, 1]
L'étape suivante est l'extraction des nombres impairs de chaque ligne du tableau. Mais il y a un hic : le 9 sur la 8ème ligne. Il résulte du 28 de la ligne précédente, puisque (28-1)/3 = 9. Je ne comprends d'ailleurs pas d'où sort ce 28. Un bug se serait-il sournoisement glissé dans mon algo ?
Il sort du 85 de la ligne précédente, puisque (85 - 1)/3 = 28. La chaine 256 > 85 > 28 > 9 est inévitable, sauf si quelqu'un intervient de l'extérieur pour dire qu'il ne faut pas en tenir compte. Et ça c'est très embêtant.
Mais if (x - 4) % 6 == 0
Ou encore if x%6 == 4
On ne veut explorer cette branche que si ça nous emmène vers un impair.
Super, merci lourran ! :-)
Maintenant on a bien le même tableau que celui de PMF ci-dessus.
Voici une variante de l'algorithme qui affiche les nombres impairs du tableau en orange, pour plus de visibilité. A noter que le tableau sera composé de chaines de caractères numériques et non plus d'entiers. Ne pas l'utiliser pour l'extraction des entiers impairs :
Cette version permet d'afficher ou non les nombres impairs en couleur en ne changeant que le booléen couleur, qui vaut True ou False (attention à l'initiale majuscule) :
Nouvelle et dernière version (?) de cet algorithme. Cette fois-ci il suffit de modifier un booléen pour que la liste des entiers impairs soit extraite du tableau (variable liste_impairs = True ou False). Avec un tableau de 12 rangées j'ai pu récupérer 23 nombres impairs (mais ce nombre augmente beaucoup plus rapidement que celui des rangées) :
5, 21, 3, 85, 13, 341, 53, 113, 17, 1365, 213, 227, 35, 453, 69, 75, 11, 5461, 853, 909, 141, 151, 23
Cependant, comme je l'expliquais dans ce message, il faudrait que PMF m'explique comment je peux les relier à la liste suivante, celle qui m'intéresse :
17, 11, 7, 9, 25, 33, 43, 57, 39, 105, 135, 185, 123, 169, 219, 159, 379, 283, 377, 251, etc.
Merci d'avance !
def tableauPMF(n, maxRangees): tableau = [[n]] for i in range(1, maxRangees): nouvRangee = [x * 2 for x in tableau[i - 1]] for x in tableau[i - 1]: if (x - 4) % 6 == 0: p = (x - 1) // 3 nouvRangee.append(p) tableau.append(nouvRangee) return tableau deb = '\033[33m' # Couleur ANSI orange # deb = "\033[91m" # Couleur rouge, si besoin fin = "\033[0m" # Reset de la couleur # Options couleur = False liste_impairs = True # Paramètres initVal = 16 maxRangees = 12 tableau = tableauPMF(initVal, maxRangees) if liste_impairs: if not couleur: nombres_impairs = [] for rangee in tableau: for nombre in rangee: if nombre % 2 == 1: nombres_impairs.append(nombre) print(f"{len(nombres_impairs)} éléments") # Afficher le nombre d'éléments print(nombres_impairs) else: print("Extraction de nombres colorés impossible") else: if couleur: for rangee in tableau: rangee_coloree = " ".join([deb + str(element) + fin if element % 2 == 1 else str(element) for element in rangee]) print(rangee_coloree) else: for rangee in tableau: print(rangee)Une précision importante : cette liste est celle des plus petits n0 dont le type est 2, 3, 4, 5, etc., le type étant le nombre de termes impairs diminué de 2 (n0 et 1). Par exemple, la suite compressée de 17 est 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, qui compte 2 termes impairs intermédiaires (13 et 5). Je précise que le type est bien entendu le même dans une suite standard et dans une suite compressée.
Pour ce script, je conseille que ton exportation suive le format suivant :
Option 1 :
1 ligne par itération en mentionnant la valeur de x
x : i
5: 5
7: 21
7 : 3
9 : 85
9 : 13
11 : 341
11 : 53
Option 2
1 ligne par valeur de x
x : i...
5 : 5
7 : 21, 3
9 : 85, 13
11 : 341, 53
12 : 113, 17
13: 1365, 213, 227, 35
Python peut certainement atteindre des valeurs de x assez grandes. De mon côté, je ne peux pas passer x = 40
Ta liste de n0 ne peut être obtenue qu'après avoir calculée LUCIE
Il faut bien avoir les valeurs de x pour chaque i
Après on peut déterminer e depuis i et x (formule déjà donnée)
quand tu as des couples (e,x) pour chaque i, il faut chercher la plus petite valeur de x pour chaque e, puis dans cette sélection, la plus petite valeur de i et tu as ton n0 pour un (x, e) donné
@PMF,
Je joins le script Python modifié pour afficher les impairs regroupés par longueur de leur suite respective. Il y a maintenant 3 options :
# Options
couleur = False # Afficher les nombres impairs en couleur
liste_impairs = True # Afficher la liste des nombres impairs
longueurs = True # Afficher la longueur de la suite de chaque nombre impair
Je suis sûr que pour me remercier tu vas mettre un point d'honneur à m'expliquer comment on passe de la suite 5, 21, 3, 85, 13, 341, 53, ... à la suite 17, 11, 7, 9, 25, 33, 43, ..., sans faire de phrases, sans prononcer le mot LUCIE, mais uniquement avec des formules.
Merci d'avance ! :-)
PS : au cas où, voici l'adresse d'un interpréteur Python (il n'affiche pas le texte en couleurs). Celui-ci affiche les couleurs.
Le script est correct pour x<=15
5 [5]
7 [3, 21]
9 [13, 85]
11 [53, 341]
12 [17, 113]
13 [35, 213, 227, 1365]
14 [11, 69, 75, 453]
La suite doit être :
5 [5]
7 [3, 21]
9 [13, 85]
11 [53, 341]
12 [17, 113]
13 [35, 213, 227, 1365]
14 [11, 69, 75, 453]
15 [23, 141, 151, 853, 909, 5461]
16 [7, 45, 277, 301, 1813]
17 [15, 93, 565, 605, 3413, 3637, 21845]
18 [29, 181, 201, 1109, 1137, 1205, 7253, 7281]
19 [9, 61, 369, 373, 401, 403, 2261, 2275, 2417, 2421, 13653, 14549, 14563, 87381]
Bravo !
Le script fonctionne jusqu'à x = 34 (maxRangees = 31) et j'ai pu checker [vérifier ?] que les 1878 impairs sont corrects
Je pense qu'il y a un souci après.
En tout cas, bravo.
Ces listes sont très longues et peuvent dépasser la capacité d'affichage de la fenêtre de résultats, auquel cas tu peux trouver trois point de suspension quelque part entre deux rangées de nombres. Par exemple, avec initVal = 16 et maxRangees = 30, je trouve ces points de suspension entre le premier terme 268 435 456 d'une rangée et 1 073 741 824 au début de la rangée suivante, alors que c'est 536 870 912 qui aurait dû figurer (c'est-à-dire le double). Cette coupure est indépendante du script, c'est la fenêtre d'affichage qui la crée de manière à pouvoir afficher le résultat jusqu'à la fin, quitte à sacrifier le milieu. La solution est peut-être celle-ci :
# Options
couleur = False
liste_impairs = True
longueurs = True
Puis décommenter la ligne 62 (supprimer le # qui figure au début), c'est-à-dire remplacer
# Afficher sur une seule ligne : print(res_trie)
par
print(res_trie) # Afficher sur une seule ligne
# for lg, n0_liste in res_trie.items():
# print(f"{deb+str(lg)+fin} {n0_liste}")
# Variante sans couleur : print(f"{lg}: {n0_liste}")
C'est-à-dire que tu commentes le code qui affiche le résultat sur plusieurs lignes de manière à le désactiver.
Résultat :
{5: [5], 7: [3, 21], 9: [13, 85], 11: [53, 341], 12: [17, 113], 13: [35, 213, 227, 1365], ...}
Pas très parlante ta terminologie. Pourquoi ne remplaces-tu pas i par n0 et x par L ?
Je viens de tester initVal = 16 et maxRangees = 40. J'ai obtenu une liste de 15408 éléments, que je joins. On y trouve L (aka x) = 43. C'est d'après moi uniquement un problème d'affichage, la longueur de ces listes semblant croître exponentiellement.
Je note juste que la seule partie que j'importe se situe après <hide>
Est-il possible de ne pas afficher toute la partie avant <hide> ?
Idéalement, il faudrait sortir comme ça:
Comme le premier terme de chaque ligne est L (aka x), on n'a pas besoin de lui donner une expression particulière
Par exemple 15: [23, 141, 151, 853, 909, 5461]
se remplace par
15;23;141;151;853;909;5461
et dans Excel la première colonne est x (L) et toutes les autres colonnes contiennent des i (n0)
Chaque nouvelle ligne est un nouveau x...
Est-ce possible?
Je reviens vers toi par rapport aux minorant et majorant d'un cluster
$\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$
Lorsque que l'on calcule tous les descendants impairs i à partir de 16 jusqu'à une certaine valeur x (longueur), on obtient une liste comme ici pour x <=17:
(Un script Python est en cours de conception par @Wilfrid pour essayer d'atteindre des valeurs x plus grandes que le vba que j'ai utilisé jusqu'ici)
il est alors possible de calculer e, le nombre d'étapes impaires :
$e=\lfloor \frac{x-log_2(i)}{log_26} \rfloor$ (corrigé)
On a alors les clusters {e,x} qui correspondent à tous les i de la liste.
Quelque soit la valeur de x atteinte, cette liste contient toujours des valeurs e de 1 à n.
Pour e = 1, on a $\text{i=}\frac{2^{x-1}-1}{3}$ pour toutes les valeurs impaires de x>=5 : i (5, 21, 85, 341, 1365...)
Je pars de l'hypothèse suivante : il existe toujours une liste d'impairs associée à une valeur de x pour trouver tous les i tel que :
$\frac{2^{x-1}-1}{3} <= i < \frac{2^{x+1}-1}{3}$ avec x impair >=5
Exemple pour x = 5, cela revient à 5 <= i < 21, soit 5, 7, 9, 11, 13, 15, 17, 19 que l'on trouve dans les clusters :
On peut dire qu'il suffit de calculer la liste jusqu'à x = 20, pour remplir tout l'intervalle 5 <= i < 21
Evidemment il va vite falloir calculer de très longues listes car pour l'ntervalle suivant 21 <= i < 85, il faudrait aller à x = 115 et e = 42
Est-ce démontrable à ton avis de dire que tout intervalle $\frac{2^{x-1}-1}{3} <= i < \frac{2^{x+1}-1}{3}$ avec x impair >=5 sera toujours rempli pour une certaine valeur de x ?
Voici l'analyse de l'intervalle $\frac{2^{n-1}-1}{3} <= i < \frac{2^{n+1}-1}{3}$ avec n = 7 soit 85 <= i < 341
les 128 impairs de cet intervalle sont distribués dans 77 clusters {e, x} :
Nous avons donc toutes les valeurs de e de 1 à 52 auxquelles sont associées 77 valeurs de x entre 9 et 143.
Le graphique ci-dessous montre les valeurs de i (points bleu) et l'intervalle minorant-majorant de chaque cluster (barres orange)
Si le graphique montre bien que $\large \frac{2^{x-e-1}}{3^e} < i < \frac{2^{x-e}}{3^e}$
la position exacte de chaque i entre le minorant et le majorant est plus mystèrieuse :
1) Ils sont plutôt positionnés vers le majorant que le minorant.
2) les i ont tendance a être rapprochés s'il y a plusieurs impairs dans le même cluster.
3) certains alignements de i sont perceptibles (l'ordonnée montre le rang des clusters classés dans l'ordre de la liste ci-dessus)
A ma connaissance, on n'a rien qui explique 1) la position précise des impairs dans l'intervalle minorant-majorant, 2) le nombre d'impairs dans le cluster 3) pourquoi les impairs "se collent" quand ils sont dans le même cluster.
Qu'en dis-tu ?
En pièce jointe les données des 77 clusters de cet intervalle