Pour faciliter la lecture toutes les listes sont entre crochets, comme dans Mathematica.
Les prédécesseurs possibles du dernier terme d’une suite de Collatz, c’est-à-dire 1, sont {1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, …}. Parmi ces nombres, ceux qui sont divisibles par 3 donneront une suite de deux termes. La suite de 21, par exemple, donne {21, 1}, et la suite de ses diviseurs se résume à un seul terme, {64} (puisque 3*21+1 = 64, qui est ensuite divisé par lui-même pour obtenir 1). On élimine donc les prédécesseurs de 1 divisibles par 3, ainsi que le premier d’entre eux, 1, ce qui donne les prédécesseurs possibles {5, 85, 341, 5461, 21845, 349525, 1398101, 22369621, 89478485, …}.
Ce qui nous intéresse est le dernier terme d’une suite de diviseurs. Pour connaître ses valeurs possibles il faut multiplier les prédécesseurs qu’on a retenus de 1 par 3 puis les incrémenter, ce qui donne {16, 256, 1024, 16384, 65536, 1048576, 4194304, 67108864, 268435456, …}.
Soit p le produit des diviseurs de n0 en tant que premier terme d’une suite impaire. Avec n0 = 29, p = 8*2*4*8*16 = 8192 = 2^13. La suite des diviseurs pouvant s’écrire {2^3, 2^1, 2^2, 2^3, 2^4}, on a bien 3+1+2+3+4 = 13. Si 2^x = 2^a*2^b*2^c = 2^(a+b+c), alors {a, b, c} est présent dans la partition de x.
Maintenant on écrit sous forme d’exposants les puissances de 2 pouvant représenter le dernier terme d’une suite de diviseurs : {16, 256, 1024, 16384, 65536, 1048576, 4194304, 67108864, 268435456, …} devient {4, 8, 10, 14, 16, 20, 22, 26, 28, …}. Pour reprendre l’exemple de p = 2^13, on sait que le dernier diviseur est 2^4, donc on retranche 4 de 13, ce qui donne 9. Les exposants de 2 des 4 premiers diviseurs sont présents dans la partition de 9 (3+1+2+3 = 9).
Construire une suite impaire de Collatz revient à trouver les parties {a, b, c, …} de l’exposant x, de sorte que 2^x = 2^a*2^b*2^c*… = 2^(a+b+c+...). Ça fonctionne avec toutes les valeurs de x > 4, donc toutes les puissances de 2 supérieures à 16. Par contre, toutes les parties de x ne permettront pas de créer une suite impaire. Pourquoi certaines seulement et pas toutes ? Pas de réponse dans l’immédiat.
Exemple avec p = 2048 = 2^11. On a 11 = 7+4 et 1+10, ce qui donne deux suites impaires de trois termes (il existe un diviseur de moins que de termes). Ce sont les suites impaires de 213 = {213, 5, 1} et 227 = {227, 341, 1}, dont la suite respective de diviseurs est {228, 16} et {2, 1024}, soit {2^7, 2^4} et {2^1, 2^10}. Les trois premières puissances de 2 pouvant représenter le dernier terme d’une suite de diviseurs sont {16, 256, 1024}, ou {2^4, 2^8, 2^10}. On a pu construire une suite impaire en retranchant 4 de 11, ce qui donnait 7, et encore une autre en retranchant 10 de 11, ce qui donnait 1. Par contre, lorsqu’on retranche 8 de 11 pour obtenir 3 on s’aperçoit qu’il n’existe aucune suite impaire dont la suite de diviseurs est {2^3, 2^8}, c’est-à-dire {8, 256} !
Voici deux fonctions permettant d’effectuer le type de calcul requis ici (syntaxe Mathematica) :
Lire divTOsuite. Exemple : divs2suite[{8, 2, 4, 8, 16}] renvoie {29, 11, 17, 13, 5, 1}, la suite impaire de 29. Je sais qu’il n’existe aucune suite impaire dont les diviseurs sont {8, 256} parce que divs2suite[{8, 256}] renvoie {679/3, 85, 1}.
La fonction suivante fait exactement la même chose, sauf qu’elle prend pour argument une liste d’exposants de 2, ce qui facilite les choses dans certains cas :
PrependTo[suite, expr] ajoute expr au début de la liste suite. exp2suite[{3, 1, 2, 3, 4}] renvoie {29, 11, 17, 13, 5, 1} comme attendu.
La fonction suivante renvoie la suite de diviseurs :
/ ; OddQ[n], placé après l’argument, signifie que celui-ci doit être impair, sinon la fonction ne fait rien. Most signifie qu’on supprime le dernier terme de la suite renvoyée par la fonction suiteImpaire, c’est-à-dire 1. IntegerExponent[argument, 2] renvoie l’exposant de 2 figurant dans la décomposition en produit de facteurs premiers de l’argument. Enfin, voici la fonction suiteImpaire :
pgp2 renvoie la plus grande puissance de 2 divisant son argument. Last renvoie le dernier élément d’une liste. AppendTo[suite, t] ajoute l’élément t à la fin de la liste suite.
Question : soit p, une puissance de 2 plus grande que 16. Si p = 2^x, lorsqu'on effectue la partition de x pourquoi certaines parties seulement permettent-elles de former une suite impaire ?