Isomorphisme de deux suites de Collatz
Bonjour,
Deux suites ou portions de suites de Collatz sont isomorphes lorsqu'elles possèdent la même structure et par conséquent le même graphe, à l'échelle près (voir la première illustration jointe). Leur structure est représentée par les valeurs successives de $u$ dans $n_{i+1}=(3\,n_i+1)/2^u$. Les deux suites que voici sont isomorphes puisque toutes deux construites à partir des valeurs successives de $u=1,1,2,3,4$ :
7, 11, 17, 13, 5, 1 (suite de référence)
4103, 6155, 9233, 6925, 2597, 487 (suite isomorphe)
Soit $A,u_1,B,u_2,C,...,u_k,F$, la suite de référence, et $M,u_1,N,u_2,O,...,u_k,R$, la suite isomorphe à celle de $A$ sur $t$ termes, dans lesquelles les lettres majuscules sont leurs termes impairs et les $u_i$ le nombre de termes pairs intermédiaires (c'est-à-dire la valeur de $u$ définie ci-dessus). Je précise que $F$ n'est pas nécessairement égal à $1$, mais représente le $t$[small]ième[/small] terme de la suite de $A$.
Pour calculer l'infinité des valeurs de $M$ on procède comme suit :
$\large \sigma =\sum\limits_{i=1}^t u_i$
$\large \Delta=2^{\sigma+1}$
$M=A+k\,\Delta\,$, où $k$ est un entier naturel non nul.
Exemple avec les 6 premiers termes de la suite de $A=7$ : les valeurs successives de $u$ étant $1,1,2,3,4\,$,
$\sigma =11$
$\Delta = 2^{12}=4096$
$M=7+k \cdot 4096=4103,8199,12295,16391,...$ avec $k=1,2,3,4,...$.
On note que l'ordre dans lequel se trouvent les $u$ successifs est sans importance puisque quel qu'il soit leur somme est constante. Pourtant, le successeur d'un terme impair étant unique, il est impossible d'intervertir deux valeurs de $u$ sans changer celle de $A$, et par voie de conséquence celle de $M$.
On peut également calculer $R$ sans passer par $M$. Pour ça je commencerai par définir la suite $T$ dont les termes sont de la forme $2 \cdot 3^{x-1}\,$, $x>0$ :
$T=2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, ...$
Chaque terme est le triple de son prédécesseur. Cette suite possède les deux ingrédients de base de toute suite de Collatz : 2 et 3. Grâce à elle on peut calculer le $t$[small]ième[/small] terme impair de la suite isomorphe à une autre sur $t$ termes. Si on connaît $F$ on calcule $R$ en posant :
$R=T(t)+F$
Si le 6ème terme impair de la suite de $A$ est $1$, celui de la suite de $M$ est $R=486+1=487$.
La suite impaire de 27 est 27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, ..., de laquelle on extrait 161, 121, 91, 137. On sait sans avoir besoin de de calculer $\Delta$ que le 4ème terme de la plus petite suite isomorphe à celle de 161 sur 4 termes est $T(4)+137=54+137=191$. Et de fait, avec $k=1$ le calcul donne $M=225\,$, dont la suite est 225, 169, 127, 191, ...
Le 4ème terme de la suite de $M$ étant $P$, on pouvait également calculer
$P=2 \cdot 3^{4-1}+137=191$
Avec $k$ égal successivement à 1, 2, 3, 4 et 5, le 1er terme des suites isomorphes à celle de 161 sur 4 termes est respectivement 225, 289, 353, 417 et 481. Leur 4ème terme est 191, 245, 299, 353 et 407. On retrouve l'équivalent de $\Delta$ puisqu'il suffit d'ajouter $T(4)$ à chaque fois.
Il est inutile d'essayer avec $t=3$ puis $2$ sur les suites de 225, 289, 353, ..., parce qu'elles ne sont plus isomorphes sur 3 et 2 termes à celle de 161 malgré le fait que leurs trois premiers $u$ soient identiques à ceux de 161. Seules les suites de 193, 225, 257, ... sont isomorphes sur 3 termes (2 $u$) à celle de 161, et seules les suites de 169, 177, 185, ... le sont sur 2 termes (1 $u$). La seconde illustration montre ceci clairement.
Enfin, si $\Delta<A$ il existe une ou plusieurs valeurs de $M<A$.
[suite dans le prochain message]
Deux suites ou portions de suites de Collatz sont isomorphes lorsqu'elles possèdent la même structure et par conséquent le même graphe, à l'échelle près (voir la première illustration jointe). Leur structure est représentée par les valeurs successives de $u$ dans $n_{i+1}=(3\,n_i+1)/2^u$. Les deux suites que voici sont isomorphes puisque toutes deux construites à partir des valeurs successives de $u=1,1,2,3,4$ :
7, 11, 17, 13, 5, 1 (suite de référence)
4103, 6155, 9233, 6925, 2597, 487 (suite isomorphe)
Soit $A,u_1,B,u_2,C,...,u_k,F$, la suite de référence, et $M,u_1,N,u_2,O,...,u_k,R$, la suite isomorphe à celle de $A$ sur $t$ termes, dans lesquelles les lettres majuscules sont leurs termes impairs et les $u_i$ le nombre de termes pairs intermédiaires (c'est-à-dire la valeur de $u$ définie ci-dessus). Je précise que $F$ n'est pas nécessairement égal à $1$, mais représente le $t$[small]ième[/small] terme de la suite de $A$.
Pour calculer l'infinité des valeurs de $M$ on procède comme suit :
$\large \sigma =\sum\limits_{i=1}^t u_i$
$\large \Delta=2^{\sigma+1}$
$M=A+k\,\Delta\,$, où $k$ est un entier naturel non nul.
Exemple avec les 6 premiers termes de la suite de $A=7$ : les valeurs successives de $u$ étant $1,1,2,3,4\,$,
$\sigma =11$
$\Delta = 2^{12}=4096$
$M=7+k \cdot 4096=4103,8199,12295,16391,...$ avec $k=1,2,3,4,...$.
On note que l'ordre dans lequel se trouvent les $u$ successifs est sans importance puisque quel qu'il soit leur somme est constante. Pourtant, le successeur d'un terme impair étant unique, il est impossible d'intervertir deux valeurs de $u$ sans changer celle de $A$, et par voie de conséquence celle de $M$.
On peut également calculer $R$ sans passer par $M$. Pour ça je commencerai par définir la suite $T$ dont les termes sont de la forme $2 \cdot 3^{x-1}\,$, $x>0$ :
$T=2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, ...$
Chaque terme est le triple de son prédécesseur. Cette suite possède les deux ingrédients de base de toute suite de Collatz : 2 et 3. Grâce à elle on peut calculer le $t$[small]ième[/small] terme impair de la suite isomorphe à une autre sur $t$ termes. Si on connaît $F$ on calcule $R$ en posant :
$R=T(t)+F$
Si le 6ème terme impair de la suite de $A$ est $1$, celui de la suite de $M$ est $R=486+1=487$.
La suite impaire de 27 est 27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, ..., de laquelle on extrait 161, 121, 91, 137. On sait sans avoir besoin de de calculer $\Delta$ que le 4ème terme de la plus petite suite isomorphe à celle de 161 sur 4 termes est $T(4)+137=54+137=191$. Et de fait, avec $k=1$ le calcul donne $M=225\,$, dont la suite est 225, 169, 127, 191, ...
Le 4ème terme de la suite de $M$ étant $P$, on pouvait également calculer
$P=2 \cdot 3^{4-1}+137=191$
Avec $k$ égal successivement à 1, 2, 3, 4 et 5, le 1er terme des suites isomorphes à celle de 161 sur 4 termes est respectivement 225, 289, 353, 417 et 481. Leur 4ème terme est 191, 245, 299, 353 et 407. On retrouve l'équivalent de $\Delta$ puisqu'il suffit d'ajouter $T(4)$ à chaque fois.
Il est inutile d'essayer avec $t=3$ puis $2$ sur les suites de 225, 289, 353, ..., parce qu'elles ne sont plus isomorphes sur 3 et 2 termes à celle de 161 malgré le fait que leurs trois premiers $u$ soient identiques à ceux de 161. Seules les suites de 193, 225, 257, ... sont isomorphes sur 3 termes (2 $u$) à celle de 161, et seules les suites de 169, 177, 185, ... le sont sur 2 termes (1 $u$). La seconde illustration montre ceci clairement.
Enfin, si $\Delta<A$ il existe une ou plusieurs valeurs de $M<A$.
[suite dans le prochain message]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
[large]Chaine d'isomorphismes[/large]
Pour illustrer mon propos je prendrai l'exemple du nombre 15239. Deux approches sont possibles :
- $M=15239$. Pour calculer la plus petite valeur de $A$, premier terme de la suite à laquelle celle de $M$ est isomorphe sur $t$ termes, il faut choisir une valeur arbitraire de $t$ (inférieure à la longueur de la suite impaire de $M$), calculer les $t$ premiers termes (impairs) de sa suite et en déduire $\Delta$. Ensuite on fera $M=M-\Delta$ autant de fois que possible, ce qui donnera $A=M$.
- $R=15239$. Ce nombre étant le $t$[small]ième[/small] terme d'une suite il ne peut pas être multiple de 3. On prend le plus grand terme de la suite $T$ qui soit inférieur à $R$ et on fait $F=R-T(t)$.
La seconde approche est la plus simple puisqu'elle ne réclame pas le calcul de $\Delta$. C'est celle qu'on retiendra. Une fois la valeur de $F$ obtenue on sait qu'il existe deux suites isomorphes l'une à l'autre sur $t$ termes dont le dernier est respectivement $R$ et $F$.$R=15239 \to F=R-T(9)=15239-13122=2117$.
On ne peut pas connaître le premier terme respectif de ces suites, parce qu'il faudrait pouvoir calculer le premier terme d'une suite dont le 9ème est 15239 ou 2117, et comme chacune est unique ce serait très compliqué. On répète donc l'opération précédente :
$R=2117 \to F=R-T(7)=2117-1458=659$.
$R=659 \to F=R-T(6)=659-486=173$.
$R=173 \to F=R-T(5)=173-162=11$.
$R=11 \to F=R-T(2)=11-6=5$.
Il est inutile de calculer les suites correspondantes, mais je le fais pour montrer leur enchainement (j'ai dû bien sûr passer par la programmation).
- 152209, 2, 114157, 3, 42809, 2, 32107, 1, 48161, 2, 36121, 2, 27091, 1, 40637, 3, 15239 est isomorphe à
- 5945, 2, 4459, 1, 6689, 2, 5017, 2, 3763, 1, 5645, 3, 2117 est isomorphe à
- 1387, 1, 2081, 2, 1561, 2, 1171, 1, 1757, 3, 659 est isomorphe à
- 545, 2, 409, 2, 307, 1, 461, 3, 173 est isomorphe à
- 29, 3, 11 est isomorphe à 13, 3, 5.
Je rappelle que chacune de ces suites étant unique, il aurait été impossible de les trouver autrement qu'en passant par une chaine d'isomorphismes.21137, 2, 15853, 3, 5945, 2, 4459, 1, 6689, 2, 5017, 2, 3763, 1, 5645, 3, 2117
1849, 2, 1387, 1, 2081, 2, 1561, 2, 1171, 1, 1757, 3, 659.
363, 1, 545, 2, 409, 2, 307, 1, 461, 3, 173.
33, 2, 25, 2, 19, 1, 29, 3, 11.
Allez, un dernier exemple pour la route : 324095
$324095-T(11)=205997\,,-T(11)=87899\,,-T(10)=48533\,,-T(10)=9167\,,-T(8)=4793\,,-T(8)=419\,,-T(5)=257,$
$-T(5)=95\,,-T(4)=41\,,-T(3)=23\,,-T(3)=5$.