Transformation continue d'une liste d'expos.

Ce fil fait suite à ce post de Serge Burckel dans lequel il proposait un algorithme équivalent à celui de Collatz mais dont le principe de fonctionnement est entièrement différent. Rappel :

$S$ est l'ensemble des exposants issus de la décomposition de $n$ en base 2, où $n$ est un entier positif impair (le $n_0$ d'une suite de Collatz). On entre ensuite dans la boucle suivante :

while length($S$) $>1$ {
$\quad S=S\cup S^+\cup $ {min($S$)}
$\quad$Supprimer les doublons de $S$
}

En sortie on obtient une valeur de $S$ de longueur 1. Pour $n=55$, $S=\{0,1,2,4,5\}$. Le résultat de la première itération sera $S=\{0,1,2,4,5,1,2,3,5,6,0\}$ suivi de $\{1,2,5,7\}$ après suppression des doublons. Si – après avoir soustrait min($S$) de tous ses termes (réduction de $S$) – on calcule la somme des puissances de 2 dont les exposants appartiennent à $S$, on obtient 83, le successeur impair de 55 dans une suite de Collatz. Aboutir à un ensemble de 1 élément revient à atteindre le 1 final, ceci dans le même nombre d'étapes.

Le problème avec ces deux algorithmes est qu'une fois $n$ ou $S$ obtenus on les transforme en quelque chose d'entièrement différent par le calcul de $3\,n+1$ ou $S=S\,\cup\,...$, si bien que le lien disparaît entre leur valeur initiale et celle qui est la leur à une étape quelconque du processus. Si on ne peut pas éviter le passage par $3\,n+1$ on peut néanmoins éliminer $S=S\,\cup\,...$ et rendre ainsi ce processus continu, puisqu'on partira de l'état initial de $S$ pour parvenir à un ensemble de 1 élément sans le transformer autrement qu'en lui appliquant les quelques règles énoncées plus bas. Ces règles ont bien entendu sur $S$ le même impact que si on avait appliqué $S=S\,\cup\,...$ suivi de la suppression des doublons. La différence est qu'elles ne le transforment pas radicalement mais modifient progressivement le nombre et la valeur de ses termes.

L'approche ensembliste n'ayant plus d'utilité, $S$ sera dorénavant une liste d'exposants, notée $[a,b,c,...]$, tous distincts et disposés par ordre croissant, si bien que $a$ est son minimum. Étant donné que $n$ est par définition impair, $a$ sera toujours égal à 0. Avec l'algorithme originel on aurait commencé par supprimer deux doublons (voir règle 3) : $\{0,...,1,...,0\}$ devient $\{1,...,1,...\}$ puis $\{2,...\}$. On remplacera donc toujours le 0 de $S$ par 2. Dans ce qui suit, le minimum de $S$ sera nommé $m$.

Un algorithme en charge de cette transformation procèderait par passes successives.

Règles, par ordre de plus haute priorité. Important : les règles 1 et 2 ne tiennent pas compte de $m$ :

1. Lorsque l'intervalle entre deux ou plusieurs termes consécutifs est $1$ on les transforme comme suit :
   $[a,b] \to [a,b+2]$
   $[a,b,c] \to [a,b+1,c+2]$
   $[a,b,c,d] \to [a,b+1,c+1,d+2]$
   $[a,b,c,d,e] \to [a,b+1,c+1,d+1,e+2]$
   $\text{etc.}$
2. Lorsque l'intervalle entre deux ou plusieurs termes consécutifs est $>1$, ou lorsqu'un terme est isolé, on en crée une copie incrémentée. Par exemple, $[...,3,6,...]$ devient $[...,3,4,6,7,...]$ ; ou encore, $[m,5]$ devient $[m,5,6]$ parce que 5 est isolé.
3. Faire $m=m+2$. Si min($S$) est maintenant en seconde position, inverser les deux premiers termes de la liste.
4. Lorsque deux termes sont égaux (doublon) on les remplace par un seul incrémenté. Par exemple, $[a,...a,...]$ devient $[...,a+1,...]$ (on supprime le premier et on incrémente le second).

Remarques :

• Si les règles 1 et 2 s'appliquent toutes deux, la règle 2 opère indépendamment de la règle 1, c'est-à-dire sans tenir compte de ce qu'elle a produit.
• La règle 4 opère sur ce qu'ont produit les règles précédentes. Elle seule prend $m$ en compte.
• Mode opératoire avec l'exemple de $[0,3,4,6,8]$ :
  1. Identification des règles à appliquer sans prise en compte de $m$ : la règle 1 s'applique à 3,4 et la règle 2 à 6,8.
  2. $[0,3,6,6,8]$ Règle 1.
     $[0,3,6,6,7,8,9]$ Règle 2.
     $[2,3,6,6,7,8,9]$ Règle 3.
     $[2,3,10]$ Règle 4 sur 6,6 puis 7,7 etc.

Exemple de processus complet. $n=57$ est représenté par $[0,3,4,5]$. Une liste indentée signifie qu'on reprend les règles depuis le début, toutes les règles applicables à une valeur donnée de $S$ l'ayant été :

$[0,3,4,5]$
$[0,3,5,7]$ Règle 1 sur 3,4,5.
$[2,3,5,7]$ Règle 3.
$\;[2,3,4,5,6,7,8]$ Règle 2 sur 3,5,7.
$[3,4,4,5,6,7,8]$ Règle 3 et inversion de 4,3 (le nouveau $m$ est 3 et doit être en première position).
$[3,9]$ Règle 4 sur 4,4 puis sur les doublons créés.
$\;[3,9,10]$ Règle 2 sur 9.
$[5,9,10]$ Règle 3.
$\;[5,9,12]$ Règle 1 sur 9,10.
$[7,9,12]$ Règle 3.
$\;[7,9,10,12,13]$ Règle 2 sur 9,12.
$[9,9,10,12,13]$ Règle 3.
$[11,12,13]$ Règle 4 sur 9,9 puis 10,10.
$\;[11,12,15]$ Règle 1 sur 12,13.
$[12,13,15]$ Règle 3 et inversion de 13,12.
$\;[12,13,14,15,16]$ Règle 2 sur 12,15.
$[13,14,14,15,16]$ Règle 3 et inversion de 14,13.
$[13,17]$ Règle 4 sur 14,14 puis sur les doublons créés.
$\;[13,17,18]$ Règle 2 sur 17.
$[15,17,18]$ Règle 3.
$\;[15,17,20]$ Règle 1 sur 17,18.
$[17,17,20]$ Règle 3.
$[18,20]$ Règle 4 sur 17,17.
$\;[18,20,21]$ Règle 2 sur 20.
$[20,20,21]$ Règle 3.
$[22]$ Règle 4 sur 20,20 puis 21,21. Liste de 1 élément. Fin.

Lorsqu'on réduit chaque valeur de $S$ précédent l'indentation et qu'on calcule la somme des puissances de 2 correspondantes, on obtient la suite impaire de Collatz de 57. A noter que $[22]$ réduit donne $[0]$, c'est-à-dire $2^0=1$.

Cet algorithme et celui de Collatz étant étroitement liés, démontrer que la transformation continue de $S$ aboutit toujours à une liste de 1 élément reviendrait à démontrer la conjecture de Collatz.

EDIT : message modifié 3 semaines plus tard car l'ordre des règles avait changé.