L'indéterminisme dans les suites de Collatz

Salut à tous,

Voici les réflexions auxquelles m'ont conduites mes recherches sur les suites de Collatz, ou problème $3n+1$. Je commencerai par quelques définitions :

1. Par "suite de Collatz" j'entends une suite ne comprenant que ses termes impairs. Elle est construite à l'aide de l'algorithme éponyme condensé.
2. Une suite descendante est construite à partir de son premier terme, tandis qu'une suite ascendante l'est à partir du dernier.
3. Plutôt que d'utiliser la notation $n_{i-1}, n_i$ je préfère utiliser $p,n$, le premier étant le prédécesseur du second.

Dans l'extrait de suite descendante $...,p,n,...$ on déduit la valeur de $n$ de celle de $p$ :

$n=\displaystyle\frac{3\,p+1}{2^u}$

Ce calcul ne présente aucune difficulté, sinon celle de connaître $u$, que l'on contourne en divisant $u$ fois le numérateur par 2.

Toujours dans la même suite, mais dans le sens ascendant, on peut calculer $p$ lorsqu'on connaît $n$ :

$p=\displaystyle\frac{2^u\,n-1}{3}$

Mais le même problème se pose : quelle est la valeur de $u$ ? Par quelle puissance de 2 doit-on multiplier $n$ pour qu'une fois le résultat décrémenté il soit divisible par 3 ? On règle ce problème en précisant ce qu'est $u$ :

$u=2\,r-m+1$, où

• $m=n\:mod\:3$.
• $r$ est le rang (ou indice) de $p$ dans la suite des prédécesseurs de $n$. Avec $n=31$, par exemple, $r=4$ lorsque $p=2645$, car les prédécesseurs de $31$ sont $41, 165, 661, 2645, ...$

Ceci permet de réécrire l'algorithme condensé de sorte que l'indétermination de $u$ soit levée, du moins dans le sens ascendant :

$n=\displaystyle\frac{3\,p+1}{\color{red}2^\color{red}u}\:,\:p=\displaystyle\frac{2^{2\,r-m+1}\,n-1}{3}$

J'ai remplacé ${2\,r-m+1}$ au dénominateur par $2^u$, suite à la remarque que je fais plus bas dans une de mes réponses.

Reprenons l'exemple de $n=31$ et voyons comment on calcule son prédécesseur $p$. On sait que $m=1$, mais pour ce qui est de $r$ sa valeur relève de notre choix. Prenons $4$ :

$2645=\displaystyle\frac{2^{2\times4-1+1}\times31-1}{3}$

Si nous avions voulu obtenir le plus petit prédécesseur de $31$ nous aurions choisi $r=1$ :

$41=\displaystyle\frac{2^{2\times1-1+1}\times31-1}{3}$

Dans le sens descendant les choses sont plus compliquées, car nous ne savons rien de

• $m$ puisqu'il est une propriété de $n$, non encore calculé.
• $r$ puisque le rang de $p$ dans la suite des prédécesseurs de $n$ n'est pas connu.

On sait néanmoins que $m=1\,\text{ou}\,2$ :

$m=1\,:\,u=2\,r-1+1=2\,r\:\rightarrow\,\text{u pair}$
$m=2\,:\,u=2\,r-2+1=2\,r-1\:\rightarrow\,\text{u impair}$

La parité de $u$ étant fonction du modulo 3 de $n$, elle nous renseigne sur la valeur de $m$. Lorsqu'on pose

$31=\displaystyle\frac{3\times2645+1}{2^8}\:,\:35=\displaystyle\frac{3\times373+1}{2^5}$

on sait que dans le premier cas $m=1\:\text{et}\:r=8/2=4$, et que dans le second cas $m=2\:\text{et}\:r=(5+1)/2=3$. Les prédécesseurs de $35$, dont le modulo 3 est 2, sont en effet $23,93,373,...$

En résumé,

• Dans le sens ascendant, $m$ est connu puisque $n$ l'est. Mais la valeur de $r$ est arbitrairement fixée à chaque étape, et on ne peut pas privilégier une valeur quelconque puisque aucune ne donnera de sens particulier au résultat. Cette variable interdit toute possibilité d'atteindre une valeur préalablement choisie de $n$ après un certain nombre d'étapes.
• Dans le sens descendant, les valeurs respectives de $m$ et de $r$ sont déterministes, liées uniquement au nombre de fois qu'on a pu diviser $3\,p+1$ par 2.

Le fait qu'il soit impossible d'atteindre une valeur préalablement fixée de $n$ dans le sens ascendant, sauf par hasard, ne signifie pas pour autant qu'il n'existe aucun lien entre le terme de départ et le terme final, mais il est du même type que celui qu'on retrouve dans tout processus aléatoire, et dans le cas présent de la succession des choix opérés de $r$, que ce soit pas un être humain ou une machine. Une manière de procéder pour éventuellement comprendre ce lien serait de générer un grand nombre de suites de Collatz (à termes impairs) puis pour chacune d'elles d'établir la liste des valeurs de $r$ qui permettent de passer du dernier au premier terme, histoire de voir s'il existe un schéma quelconque, un cycle. Mais il y a un problème : pour établir la liste des valeurs de $r$ dans le sens ascendant il suffit d'inverser celle des valeurs de $u$ dans le sens descendant, puis d'en extraire chaque valeur de $r$ comme expliqué plus haut. Or, personne à ma connaissance n'a jamais constaté le moindre schéma ou cycle dans la succession des valeurs de $u$. La construction d'une suite de Collatz est donc bien un processus déterministe dans le sens descendant, et stochastique dans le sens ascendant.

PS : ceux qui désirent savoir d'où sort $u=2\,r-m+1$ peuvent consulter mon document mis à jour aujourd'hui à partir du bas de la page 6.