Lemme de Higman et Syracuse

Remarque : on peut aussi écrire les nombres dans les deux bases l'une après l'autre.

La multi-base 4,7 semble convenir alors. Par exemple $27=[1_4,2_4,3_4,3_7,6_7]$.

Dans une base simple, cela semble en effet se bloquer. Là, mon programme en est à tester la base 331.

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.

Remarquez aussi que pour des "petites" bases simples, il semble n'exister qu'un nombre fini de contre-exemples.

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.

Tous ces tests continuent d'être valides au delà des 200 millions....

@PMF : oui...quand on n'a pas d'idées... on en cherche par l'expérimentation.

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>>.

Une petite précision pour bien me faire comprendre.

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}$

Dans la même lignée...une autre idée.

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)

....au delà des 7 millions...

...au delà des 30 millions...

...au delà des 500 millions...

Là on peut commencer à chercher une preuve. C'est une très bonne piste, à mon avis.