Lemme de Higman et Syracuse
dans Shtam
Voici une autre approche de cette conjecture par le Lemme de Higman qui dit ceci :
Une suite infinie de mots sur un alphabet fini contient nécessairement un sous-mot d'un mot suivant dans la suite.
Sous-mot au sens de sous-suite comme par exemple ABC est sous-mot de xAyzBbbaCef.
L'idée est alors de représenter les suites de Syracuse $n=f^0(n),f^1(n),f^2(n),...$ et si on peut montrer qu'il n'y a pas de $f^i(n)$ sous-mot de $f^j(n)$ avec $0\le i<j$, alors cette suite ne peut pas être infinie (si on s'arrête à $1$).
Si on écrit les nombres en base 2, c'est rappé par exemple $3=[1,1]_2$ devient $5=[1,0,1]_2$.
C'est rappé aussi dans les bases suivantes....par exemple en base $10$ : $7=[7]_{10}$ devient $17=[1,7]_{10}$
ou encore en base $124$ où $31=[31]_{124}$ devient $155=[1,31]_{124}$
Mais....peut-être qu'en base....$125=5^3$ ???? à voir....
Bon, en fait non plus en base 125 : $1772655=[113, 56, 30]_{125}$ devient $5678905=[2, 113, 56, 30]_{125}$
Alors y-a-t-il une telle bonne base ? 229 ? Bon, là on arrive à des arguments probabilistes qui jouent en faveur du "vrai injustifiable".
Cela ne prouverait pas directement la conjecture (convergence vers $1$) mais au moins l'absence de suite infinie ou de cycles autres que celui de $1$.
Une suite infinie de mots sur un alphabet fini contient nécessairement un sous-mot d'un mot suivant dans la suite.
Sous-mot au sens de sous-suite comme par exemple ABC est sous-mot de xAyzBbbaCef.
L'idée est alors de représenter les suites de Syracuse $n=f^0(n),f^1(n),f^2(n),...$ et si on peut montrer qu'il n'y a pas de $f^i(n)$ sous-mot de $f^j(n)$ avec $0\le i<j$, alors cette suite ne peut pas être infinie (si on s'arrête à $1$).
Si on écrit les nombres en base 2, c'est rappé par exemple $3=[1,1]_2$ devient $5=[1,0,1]_2$.
C'est rappé aussi dans les bases suivantes....par exemple en base $10$ : $7=[7]_{10}$ devient $17=[1,7]_{10}$
ou encore en base $124$ où $31=[31]_{124}$ devient $155=[1,31]_{124}$
Mais....peut-être qu'en base....$125=5^3$ ???? à voir....
Bon, en fait non plus en base 125 : $1772655=[113, 56, 30]_{125}$ devient $5678905=[2, 113, 56, 30]_{125}$
Alors y-a-t-il une telle bonne base ? 229 ? Bon, là on arrive à des arguments probabilistes qui jouent en faveur du "vrai injustifiable".
Cela ne prouverait pas directement la conjecture (convergence vers $1$) mais au moins l'absence de suite infinie ou de cycles autres que celui de $1$.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
D'ailleurs, il y a un contrexemple pour 229 aussi : $7498399=[142,226,23]$ qui donne $55534355=[4,142,226,23]$
Alors, je continue l'idée....et si on écrivait les nombres en plusieurs bases combinées ? why not !
On écrit de manière imbriquée les écritures en bases $b1$ et $b2$.
Par exemple en bases $5,3$...et là...on dirait que ça marche.....à suivre.
Par exemple 27 en base 5,3 s'écrit : $[0, 1, 1, 0, 0, 0, 2, 0]_{5,3}=[0_5, 1_3, 1_5, 0_3, 0_5, 0_3, 2_5, 0_3]$ parce que
en base 5 c'est $[1,0,2]$
en base 3 c'est $[1,0,0,0]$
On obtient éventuellement des $0$ au début dans la base (la plus grande) "trop courte" par rapport à l'autre (la plus petite).
Remarque : on peut distinguer les deux classes de chiffres pour les deux bases.
La multi-base 4,7 semble convenir alors. Par exemple $27=[1_4,2_4,3_4,3_7,6_7]$.
Mais dans une base double comme 4,7....ça continue de fonctionner
Idem pour 3,5 si on imbrique les mots. Cela revient juste à rajouter des $0_5$ en base 5 pour obtenir la même longueur qu'en base 3.
Dans les 3 cas, le programme de tests a dépassé les 10 millions.
Ce que je remarque de mon côté avec une représentation des chemins sous forme d'un graphe où les valeurs des entiers sont remplacées par un couple $i(n),p(n)$ est une hyper concentration sur des sommets particuliers. Vu de cette façon les suites de Syracuse forment des "mots" présentant énormément de parties communes et très rarement des mots exotiques.
Si par hasard il y a une relation entre ta méthode et la mienne tu devrais trouver beaucoup de mots se ressemblant beaucoup.
Pour préciser la notion de sous-suites et pour ceux qui aiment programmer et tester, voici la procédure :
sous-suite(s,t)
a:=long(s); b:=long(t);
tant que (0<a<=b) faire
....si s[ a ] = t[ b ] alors a:=a-1;
....b:=b-1;
si a=0 alors vrai sinon faux.
Autre chose testée : prenons pour $n$ impair les successeurs impairs $f^0(n),f^1(n),...$ modulo $40.n$. Ils semblent tous différents.
C'est vérifié pour l'instant à plus de $80$ millions.
Ces tests sont réalisés pour donner des intuitions sur ce qui pourrait être vrai mais surtout pour éliminer ce qui est faux.
Je cherche aussi des relations de congruences. Exemple.
Pour tout nombre $n>1$ qui devient $n'<n$ en effectuant $d$ divisions par $2$ et $m$ opérations $3x+1$ alors :
pour tout $k\ge 0$, les nombres de la forme $2^d.k+n$ deviennent $3^m.k+n'$ et ces derniers nombres sont plus petits puisque $3^m<2^d$ et $n'<n$.
En effet, $3^m$ est plus petit que ce qui est obtenu en effectuant $m$ fois l'opération $3x+1$ et ceci est plus petit que ce qui est obtenu en effectuant $d$ fois l'opération $2x$... sinon $n'$ ne serait pas inférieur à $n$.
Exemple : $3\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2$ : $d=4$ et $m=2$.
Donc pour tout $k\ge 0$ : $16k+3\rightarrow 9k+2$
Conclusion : quand la conjecture est vraie pour $n$, elle l'est aussi pour toute une classe de nombres. Reste à tout couvrir. Pour cela, on peut aussi considérer des chemins inverses. Dans l'exemple : $16k+3\rightarrow 24k+5$. Donc, si la conjecture est vérifiée pour les nombres de la forme $16k+3$, alors elle est aussi vraie pour les nombres de la forme $24k+5$. Et inversement, si la conjecture est vérifiée pour les nombres de la forme $24k+5$, alors elle est aussi vraie pour les nombres de la forme $16k+3$.
Reste à faire une preuve complète dans... <<le bon ordre>>. Et le plus difficile est de dénicher ce <<bon ordre>>.
Tu as là une sorte de formule de chemins "type" et ce que j'observe de mon côté c'est justement une structure de chemins qui convergent pour former des "tronçons" en allant vers 1. Par exemple dans ma bdd 40% des entiers passent par 911 en étape 12, 93% arrivent sur 5 ...
Je vais essayer de trouver plus d'exemples et faire quelques calculs avec ta formule de congruence.
on a tous ces n' à partir de k = 1 : 19, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 195, 211, 227, 243, 259, 275, 291, 307...
Il faudrait comparer leurs chemins, leurs clusters et comment ils se connectent dans le graphe des $i(n),p(n)$
On doit normalement y trouver une "signature" de cette relation de congruence
2^d * k + n
> 3^m * k + n'.
Tu ne peux pas dire que le second terme est toujours plus petit que le premier. Si c'était vrai, la conjecture serait résolue !
La conjecture initiale de Collatz est équivalente à la suivante :
pour tout nombre $n>1$, il existe un $k$ tel que $m=f^{(k)}(n)<n$.
Par induction, cela montre bien que $n$ converge vers $1$.
Maintenant, on peut aussi étendre cet énoncé en :
a) considérant un autre bon-ordre $<$ que le "naturel" sur les entiers
b) considérant des $m<n$ dans la "toile" de $n$ c'est à dire dans un chemin fait de $f$ et d'inverses $f^{-1}$
Considérons les écritures en base $B$.
Ce serait souhaitable que l'écriture d'un nombre $n$ ne soit pas préfixe de celle d'un de ses successeurs $m=f^k(n)$.
Précision : on ne considère que la restriction aux nombres impairs.
Pour $B=2$, ce n'est pas le cas puisque $27=1\ 1\ 0\ 1\ 1_2$ devient $445=1\ 1\ 0\ 1\ 1\ 1\ 1\ 0\ 1_2$
Pour $B=3$, ce n'est pas le cas puisque $27=1\ 0\ 0\ 0_3$ devient $251=1\ 0\ 0\ 0\ 2\ 2_3$
Pour $B=4$, ce n'est pas le cas puisque $27=1\ 2\ 3_4$ devient $445=1\ 2\ 3\ 3\ 1_4$
etc...
Pour $B=11$, ce n'est pas le cas puisque $147=1\ 2\ 4_{11}$ devient $1619=1\ 2\ 4\ 2_{11}$
etc...
Pour $B=17$, ce n'est pas le cas puisque $63=3\ 12_{17}$ devient $1079=3\ 12\ 8_{17}$
Mais pour $B=18=2.3^2$...serait-ce le cas ? en tout cas, pas de contre exemple pour l'instant. Un petit pas vers un ordre ?
Notez qu'il n'y a pas aller au delà de $147$ pour éliminer les bases $B\le 17$. La base $B=18$ "tient le coup" au delà des 5 millions...(à suivre)
bien sûr, ceci n'est qu'une observation obtenue par programmation...encore faut-il une preuve.
Ceci montrerait au moins qu'il n'y a pas d'autres cycles et pourrait initialiser une preuve simple.
On peut se lancer dans des conjectures alors.
Conjecture : pour tout $n$ impair et $m=f^k(n)$ impair, il n'existe pas de nombres $h,r$ tels que $m=18^h.n+r$ avec $18^h>r\ge 0$.
Là on peut commencer à chercher une preuve. C'est une très bonne piste, à mon avis.
Bien.
Et quid de 19, 20, ... 24, 27, 36, 81 ...
Si ces nombres tiennent aussi jusqu'à quelques centaines de millions, ou s'ils explosent très vite comme les nombres inférieurs à 18, la réflexion ne sera pas la même.
Si les non-multiples de 18 explosent très vite, alors que les multiples de 18 tiennent beaucoup plus longtemps, c'est une piste d'explication.
J'ai un peu l'impression qu'on est dans un raisonnement assez proche de celui qui dit : 's'il y a des cycles non triviaux, ces cycles auront une longueur supérieure à .... '
Et la propriété qui est derrière tout ça, c'est que pour trouver des couples (a,b) tels que $2^a/3^b$ soit très proches de 1, il faut aller chercher a et b assez grands.
Pour 'mesurer' une base, on peut regarder quand arrive le premier accident, c'est ce que tu fais. On peut aussi compter le nombre d'accidents inférieurs à 100000.
Et peut-être que sur ce critère, on va voir que 9 ou 12 explosent vite, mais qu'ils ont très peu d'accidents, moins que les nombres comme 11 ou 13 ...???