Conjecture de Syracuse

[suite du précédent]

D'ailleurs si on pose

$n_2=\dfrac{3\;n_1+1}{p}$ et $n_1=\dfrac{n_2\;p-1}{3}$

et qu'on se demande dans quelles conditions $n_1=n_2$, on trouve

$p=\dfrac{3\;n_1+1}{n_1}$

On sait que $p$ est pair puisque c'est une puissance de 2 :

$n_1$ pair : $3\;n_1+1$ impair $\to$ impossible.
$n_1$ impair : $3\;n_1+1$ pair $\to$ $p$ pair.

$n_1$ doit donc être impair et le quotient égal à 2, 4, 8, 16, ... Quelles valeurs de $n_1$ satisfont à ces conditions hormis $n_1=1$ ?

Je préfère en rester aux suites composées de termes impairs uniquement, plus simples à gérer. Ce dont j'ai parlé ci-dessus équivaut donc au cycle de longueur 1 $n_1, n_1, n_1, ...$, et en l'occurrence 1, 1, 1, 1, ...

Soupçonner l'existence de cycles de longueur supérieure à 1 est contraire à l'idée qu'on se fait d'un arbre des suites dans lequel chaque terme impair est unique. Le terme impair $n$ possédant une infinité de prédécesseurs calculables, il existe une infinité de chemins menant à lui, mais il n'en demeure pas moins unique. Il possède un successeur unique, qui lui-même possède un successeur unique, etc., parce que l'algorithme de Collatz n'admet qu'une seule solution à chaque étape.

Prenons l'extrait d'une suite $..., n_1, n_2, ..., n_L, n_1, ...$ dans lequel on observerait la formation du cycle de longueur $\small{L}\:$$n_1, ..., n_L$. La figure suivante, dans laquelle $p_r$ est le prédécesseur de $n_1$ de rang $r$, montre ce qui se passerait :


On pourrait penser qu'avec le cycle $\color{red}{p_1}, n_1, n_2, ..., \color{red}{p_3}, n_1$ il n'y aurait pas de duplication de terme, mais le problème vient du fait que la suite dans laquelle il serait supposé figurer appartient à l'arbre des suites, et que le second $p$ étant toujours dupliqué, l'arbre contiendrait deux fois le même terme impair, ce qui par définition est impossible. Par conséquent il ne peut pas exister de cycle de longueur > 2, parce que $p, n, p, n, ...$ pourrait éventuellement exister (pas de duplication). Il faudra approfondir la question.

Bon, il est possible que mes explications n'étaient pas suffisamment claires. Je reprends, en commençant par insister sur le fait qu'ici il n'est question que de suites de Collatz constituées de leurs seuls termes impairs.

Prenons deux termes consécutifs $p$ et $n$. Sachant que $p$ est le prédécesseur de $n$, lorsqu'on cherche à calculer $n=(3\;p+1)/2^u$ ou $p=(2^u\;n-1)/3$ on se heurte toujours à l'inconnue qu'est $u$. Mais lorsqu'on pose

$p_r=\dfrac{2^{2\,r-(m-1)}\;n-1}{3}$, avec $r$ entier naturel > 0 et $m=n\;\text{mod}\;3$,

on peut calculer tous les prédécesseurs de $n$. Par exemple, quels sont les 5 premiers prédécesseurs de 23 ? $m=$ 2 et $r=$ successivement 1, 2, 3, 4, 5, ce qui donne $p=$ 15, 61, 245, 981, 3925. Un prédécesseur sur 3 est un multiple de 3, mais dans ce qui suit on admettra qu'ils ont été éliminés.

Passons maintenant au cycle $n_1, n_2, ..., n_L, n_1, n_2, ..., n_L, n_1,$ etc., donc de longueur $\small{L}$, que je fais maintenant débuter par le prédécesseur de $n_1$ : $p_x, n_1, n_2, ...$ et ensuite ? $n_L$ étant le prédécesseur de $n_1$, il appartient nécessairement à l'ensemble des prédécesseurs de celui-ci, et le cycle s'écrit $\color{gray}{p_x,} n_1, n_2, ..., p_y$. La suite complète, terminée par $p_y$, peut-elle figurer dans l'arbre des suites ? Bien sûr que non puisque $p_y$ y figure déjà, et que par définition aucun entier impair ne peut se trouver en double exemplaire dans cet arbre ! Si cette suite ne peut pas figurer dans l'arbre elle n'existe tout simplement pas.

Si on commençait à admettre la duplication de termes impairs il faudrait ensuite se demander combien d'exemplaires peuvent se trouver dans l'arbre. Mais non, cette question serait inutile puisque l'arbre aurait cessé d'exister !

Reste le cas du cycle de longueur 2 $p, n, p, n, ...$, qui ne souffre d'aucune duplication et pourrait de ce fait exister. Mais comme je l'ai dit plus haut, il faudrait que $p$ soit à la fois le prédécesseur et le successeur de $n$, ce qui n'est possible que lorsque $p=n=1$.

Conclusion : il n'existe aucun autre cycle que 1, 1, 1, ...

@lourran,

Je souscris à ton argument selon lequel il n'a jamais été démontré que 1 se trouvait à la racine de l'arbre, malgré les très fortes présomptions qui pèsent en sa faveur. Le problème n'est cependant pas là.

On peut se représenter l'ensemble des prédécesseurs $p_r$ de $n_1$ comme une bande verticale. Construire une suite de Collatz revient ni plus ni moins à passer d'une bande à l'autre. La position verticale de la trajectoire lors de son passage sur une bande n'a aucune influence sur la position qui sera la sienne à son arrivée sur la bande suivante, puisque l'algorithme de Collatz n'admet qu'un seul successeur. L'indéterminisme fait son apparition lorsqu'il s'agit de construire une suite à l'envers : à chaque étape on doit choisir au hasard la position verticale de la trajectoire sur la bande précédente.


Le prédécesseur du premier terme d'un cycle appartient nécessairement à la même bande que son dernier terme. La seconde bande est une chimère, il est en réalité impossible qu'elle soit là, et ceci reste valable quelle que soit la racine de l'arbre.

Je pensais qu'après trois approches différentes j'aurais réussi à me faire comprendre, mais je constate que malheureusement ce n'est pas le cas. Si je trouve une quatrième manière d'expliquer tout ceci je ne manquerai pas de la poster !