Il ne s’agit plus ici de suites de Collatz impaires mais de suites dites compressées, qu’on obtient en appliquant l’algorithme suivant à n0 :
Pour calculer une valeur de n0 produisant une suite de longueur (ou nombre de termes) L donnée il fallait jusqu’à présent procéder en commençant par 1 et en remontant jusqu’à la valeur adéquate de n0, ce qui posait le problème de la divisibilité potentielle de chaque prédécesseur par 3. L’idéal est donc de calculer directement cette valeur de n0. Je vais montrer comment y parvenir.
Lorsqu’on construit la liste des entiers impairs dont la suite compressée est de longueur L, on doit les tester tous à partir de 3 (par exemple) jusqu’à une limite supérieure arbitraire au-delà de laquelle on ne sait pas s’il en existe d'autres. Je définirai plus loin cette limite, mais dans l’immédiat voici à titre d’exemple ce qu’on obtient lorsqu’on recherche les valeurs de n0 qui produiront une suite compressée de longueur 17 :
25, 77, 81, 241, 245, 267, 725, 739, 753, 803, 805, 2261, 2275, 2417, 2421, 7253, 7281, 21845
On peut classer ces nombres ainsi :
Le type de la suite (et par extension de n0 lui-même) correspond au nombre de termes impairs intérieurs qu’elle contient, n0 et 1 n’étant pas comptabilisés puisqu’ils sont communs à toutes les suites. Le type 0 ne contient aucun terme impair intérieur ; cette valeur de n0 est de la forme (2^(L-1) – 1)/3 et n’est présente que lorsque L est impair. Notons que la valeur correspondante de n0 est sensiblement 3 fois plus grande que celle de son prédécesseur dans la liste.
Les valeurs de n0 produisant des suites de type 0 et 1 ne peuvent pas se calculer de la même manière que celles produisant des suites d’autres types. Voici comment on les obtient (syntaxe Mathematica) :
Lorsqu’on désire calculer toutes les valeurs de n0 dont la suite compressée est de longueur L, le plus grand entier impair à tester est Max(n0max(L)). Aller jusqu’à n0 de type 0, lorsque L est impair, entraine toutefois une augmentation importante du temps de calcul, surtout qu’il n’existe aucune valeur pertinente de n0 entre la plus grande de type 1 et celle en question.
Pour continuer avec notre exemple, n0max(17) = {7253, 7281, 21845}
Avec L pair : n0max(18) = {13653, 14549, 14563}
Calcul des valeurs de n0 de type supérieur à 1
A titre d’exemple, les valeurs de n0 de type 2 produisant des suites de longueur L = 10, 11, 12, 13, 14, …, 20 sont 17, 35, 69, 141, 277, 565, 1109, 2261, 4437, 9045, 17749. Ces nombres sont définis par la relation de récurrence suivante :
Pour calculer la valeur de n0 de rang r donné dans cette suite d’entiers, il est donc nécessaire de connaître la valeur de (a1, a2, a3) ainsi que la longueur de la suite produite par n0 = a1. Pour reprendre l’exemple précédent, si on cherche la valeur de n0 produisant une suite de type 2 de longueur 15, son rang r sera égal à 15 – 10 +1 = 6, ce qui donnera n0 = 565.
Il n’existe malheureusement pas de formule magique donnant (a1, a2, a3) pour un type de suite donné. Il faut effectuer ce calcul à la main (je l’ai fait avec l’aide d’un bon algorithme, mais ça m’a quand même pris beaucoup de temps). Le tableau suivant contient tous les quadruplets nécessaires au calcul d’une valeur de n0 produisant une suite compressée de type 2 à 50 et de la longueur désirée. Ils sont composés comme suit :
Ce qui frappe lorsqu’on observe ce tableau, ne serait-ce que les valeurs successives de L min, c’est la totale incohérence des données qu’il contient. Il faut cependant admettre que des données initiales réellement incohérentes ne conduiraient pas à quelque chose d’aussi ordonné, ce qui donne à penser qu’il existe sans doute une structure sous-jacente. Mais si c’est le cas elle est bien cachée…
Le tableau est suivi de la fonction suiteLt(L, t), qui renvoie la suite compressée de longueur L et de type t.
Pour retrouver notre valeur précédente de n0 = 565 il suffit de faire suiteLt(15, 2), et on obtient
565, 848, 424, 212, 106, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1
Sa longueur est bien 15 et elle contient 2 termes impairs intérieurs. Si on veut produire une suite de type 2 et de 60 termes, on obtiendra une suite comportant (en comptant n0 et 1) 60 – 4 = 56 termes pairs et une très grande valeur de n0, comme suiteLt(60, 2), qui renvoie
19515598385272149, 29273397577908224, 14636698788954112, 7318349394477056, 3659174697238528, 1829587348619264, …, 832, 416, 208, 104, 52, 26, 13, 20, 10, 5, 8, 4, 2, 1
A l’inverse, suiteLt(46, 23) produit une petite valeur de n0 :
111, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1
En règle générale, l’ordre de grandeur de n0 est proportionnel à celui de L – t.
En raison du fait que l'algorithme s’appuie sur un tableau de données, toutes valeurs de L et de t données produiront toujours la même sortie. Néanmoins, j’ai pu observer que certains types permettent de produire plusieurs valeurs (a1, a2, a3), alors que d’autres types ne permettent qu’une seule configuration. On constate là encore une grande disparité de comportements, sans logique apparente.
Les utilisateurs de Mathematica 10 peuvent télécharger le notebook correspondant. Il se peut qu'il fonctionne également dans les versions antérieures.
PS : un modérateur aurait-il l'obligeance de supprimer le sujet "Partition d'un entier", qui n'a plus lieu d'être ? Merci d'avance !