Dans ce volet bleu sur le problème $3n+1$, nous montrons qu’il n’existe aucun cycle de longueur 5 pour la transformation de Collatz sur les entiers positifs.

En fait on peut montrer plus : il n’existe aucun tel cycle de longueur comprise entre 4 et environ 17.000.000.000 (17 milliards), comme on le verra dans un article ultérieur.

L’intérêt de cette preuve séparée pour la longueur 5 est d’être assez élémentaire, tout en contenant déjà l’idée essentielle pour la suite : la mise en évidence d’une équation très contraignante associée à un cycle. Pour aller plus loin, c’est sur piste rouge qu’il faudra s’aventurer, en s’équipant de logarithmes et d’approximations rationnelles ; il n’en sera nul besoin ici.

Quelques rappels

Rappelons la définition de la transformation de Collatz, présentée dans le volet vert de cette série [1] : si $n$ est un entier pair, on le transforme en $n/2$ ; s’il est impair, on le transforme en $3n+1$.

On symbolise cette transformation par une petite flèche. Par exemple, $10 \rightarrow 5$ (qu’on peut lire « 10 va sur 5 ») et $5 \rightarrow 16$. La règle générale s’écrit donc $n \rightarrow n/2$ ou $n \rightarrow 3n+1$, suivant que $n$ est pair ou impair.

La trajectoire de $n$ est la suite obtenue en partant de $n$ et en lui appliquant la transformation de Collatz de façon répétée. Par exemple, la trajectoire de 1 est la suite 1,4,2,1, ..., qui est donc un cycle de longueur 3.

Le problème de Collatz consiste à déterminer s’il est vrai que la trajectoire de n’importe quel nombre entier positif $n$ de départ tombe forcément sur 1.

Cycles dans les entiers négatifs

La transformation de Collatz peut très bien s’étendre aux entiers négatifs, avec exactement les mêmes formules :

• si $n$ est pair, on l’envoie sur $n/2$ ;

• si $n$ est impair, on l’envoie sur $3n+1$.

Par exemple, la trajectoire de $-1$ est un cycle de longueur 2 :
\[-1 \rightarrow -2 \rightarrow -1.\]
La trajectoire de $-5$ donne un autre cycle, cette fois-ci de longueur 5 :

Retour aux entiers positifs

Pourrait-il aussi exister un cycle de longueur 5 dans les entiers positifs ? La réponse est non. Pour le prouver, nous procéderons par l’absurde : on suppose au contraire qu’il en existe un ; puis on le manipule comme on peut, révélant ainsi une équation qui lui est associée ; et on conclut en constatant que cette équation est insoluble.

Le plus petit élément d’un cycle

Commençons par une remarque à la fois simple et utile : pour un hypothétique cycle de la transformation de Collatz sur les entiers positifs, son plus petit élément est forcément impair.

En effet, notons $C$ ce cycle et $m$ son plus petit élément. Alors bien sûr, $C$ est la trajectoire de $m$. Notons maintenant $m'$ le nombre obtenu à partir de $m$ par transformation de Collatz. Alors $m'$ est

• lui aussi dans $C$, puisque $C$ est la trajectoire de $m$ ;

• plus grand que $m$, puisque $m$ est minimal dans $C$.

Or si par l’absurde $m$ était pair, on aurait $m'=m/2$ qui est plus petit que $m$ : contradiction. Donc $m$ est bien impair.

Le cas de longueur 5

Considérons maintenant un hypothétique cycle de longueur 5 dans les entiers positifs. On notera ses cinq éléments distincts deux à deux $a_1,a_2,a_3,a_4,a_5$, donnant

par transformation de Collatz.

Quitte à renommer les indices, on peut supposer que le plus petit des cinq est $a_1$. Alors $a_1$ est forcément impair par la remarque ci-dessus, et en particulier $a_2=3a_1+1$. Notons encore que $a_1$ est différent de 1, puisque la trajectoire de 1 donne un cycle de longueur 3 et non 5. Donc $a_1$ est supérieur ou égal à 3.

Stabilité par transformation de Collatz

Si on applique la transformation de Collatz à la liste \[a_1,a_2,a_3,a_4,a_5\] des éléments du cycle, on obtient la même liste décalée d’un cran, puisque c’est un cycle justement : \[a_2,a_3,a_4,a_5,a_1.\]
On exprime cela en disant que ce cycle est stable par transformation de Collatz. C’est évident, mais ce sera crucial pour la suite.

Répartition des pairs et des impairs

Pour savoir concrètement comment la transformation de Collatz agit sur $a_1,\ldots,a_5$, on doit savoir lesquels parmi eux sont pairs et lesquels sont impairs. On sait déjà, par minimalité de $a_1$ dans ce cycle, que $a_1$ est impair. Quant aux quatre autres termes, on va montrer par étapes successives que

• $a_2$, $a_4$ et $a_5$ sont pairs ;

• $a_3$ est impair.

En voici la preuve.

(1) Puisque $a_1$ est impair, il suit que $a_2=3a_1+1$. Donc $a_2$ est pair.

(2) Il suit que $a_3=a_2/2 = (3a_1+1)/{2}$. Se pourrait-il que $a_3$ soit pair ? Si c’était le cas, on aurait alors $a_4=a_3/2$ et, si on enchaîne avec ce que l’on sait déjà sur $a_2$ et $a_1$, cela donnerait
\[ \begin{array}{rcl} a_4 & = & \frac{a_3}2\\ & = & \frac{a_2}4\\ & = & \frac{3a_1+1}{4}. \end{array} \]
Mais cette relation dirait que $a_4$ vaut environ les trois quarts de $a_1$ ; il serait donc plus petit que $a_1$ (puisque celui-ci est supérieur ou égal à 3), en contradiction avec la minimalité de $a_1$. L’hypothèse que $a_3$ est pair conduisant à une contradiction, on conclut que $a_3$ est forcément impair.

(3) Puisque $a_3 \rightarrow a_4$, il suit que $a_4=3a_3+1$, et donc que $a_4$ est pair. De plus, comme $a_4 \rightarrow a_5$, il suit que $a_5=a_4/2$.

(4) Pour finir, $a_5$ est pair. En effet, d’une part on a $a_5 \rightarrow a_1$, et de l’autre $a_5$ est plus grand que $a_1$ (toujours par minimalité de $a_1$). La seule possibilité est que $a_5$ soit pair et donc que $a_1=a_5/2$. Car dans le cas contraire, $a_1$ serait plus grand que $a_5$, ce qui est exclu.

Nous connaissons maintenant l’exacte répartition des pairs et des impairs dans notre cycle. Résumons les formules obtenues en chemin, exprimant chaque terme du cycle en fonction du précédent :
\[ \begin{array}{rcl} a_1 & = & \frac{a_5}{2}\\ a_2 & = & 3a_1+1\\ a_3 & = & \frac{a_2}{2}\\ a_4 & = & 3a_3+1\\ a_5 & = & \frac{a_4}{2}. \end{array} \]

Le produit des termes du cycle

L’étape suivante consiste à prendre le produit de ces 5 termes, qu’on appellera $P$. En les lisant du côté gauche de la colonne d’égalités ci-dessus, on obtient
\[P\, = \, a_1 a_2 a_3 a_4 a_5.\]
En les lisant maintenant du côté droit — et avec la première ligne lue en dernier —, on obtient toujours $P$ bien sûr, mais exprimé différemment :
\[P\, = \, (3a_1+1) \frac{a_2}{2} (3a_3+1) \frac{a_4}{2} \frac{a_5}{2} .\]
C’est l’existence même de ces deux expressions différentes de $P$ qui donne lieu à l’équation annoncée. La voici donc, dans une première version brute :
\[ a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) \frac{a_2}{2} (3a_3+1) \frac{a_4}{2} \frac{a_5}{2}. \]

Quelques manipulations

Cette équation contient des informations intéressantes. Mais pour les révéler, il faut s’autoriser quelques manipulations algébriques. Rassemblons d’abord les trois dénominateurs $2$, ce qui donne $2 \times 2 \times 2 = 8$ :
\[ a_1 a_2 a_3 a_4 a_5 \, = \, \frac{(3a_1+1) a_2 (3a_3+1) a_4 a_5}{8}. \]
Puis chassons le dénominateur $8$ du côté droit, en multipliant simplement les deux côtés de l’égalité par $8$ :
\[ 8 a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) a_2 (3a_3+1) a_4 a_5. \]
Dans le terme de droite, intervertissons $a_2$ et son voisin de droite :
\[ 8 a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) (3a_3+1) a_2 a_4 a_5. \]
On voit que $a_2a_4a_5$, qui est non-nul, est un facteur commun aux deux côtés de l’égalité. On peut donc s’en débarrasser en divisant le tout par ce facteur, ce qui donne :
\[ 8 a_1 a_3 \, = \, (3a_1+1) (3a_3+1). \]
Divisons maintenant les deux côtés par $a_1a_3$, qui est lui aussi non-nul :
\[ 8 \, = \, \frac{(3a_1+1)}{a_1} \frac{(3a_3+1)}{a_3}. \]
En appliquant l’identité générale \[\frac{a+b}c = \frac ac + \frac bc\] aux deux facteurs du terme de droite, on obtient finalement :

\[ 8 \, = \, (3+\frac1{a_1}) (3+\frac1{a_3}). \]

C’est l’équation annoncée, sous sa forme épurée, associée à n’importe quel hypothétique cycle de longueur 5.

Fin de la preuve

Nous pouvons maintenant conclure : comme $a_1$ et $a_3$ sont supposés positifs, l’équation ci-dessus est impossible à satisfaire, puisqu’à droite on obtient un nombre supérieur à 9, alors qu’à gauche on n’a que 8.

On vient de prouver que la transformation de Collatz n’admet aucun cycle de longueur 5 sur les entiers positifs.

Une apparente contradiction

Il y a une bizarrerie à comprendre : le développement ci-dessus reste valable sur les entiers négatifs, quitte à remplacer les comparaisons de grandeur par des comparaisons de grandeur en valeur absolue [2]. Comment se fait-il que, malgré cela, il existe bel et bien un cycle de longueur 5 dans les entiers négatifs ?

La solution de cette apparente contradiction tient à l’ultime argument de la preuve : bien qu’insoluble dans les entiers positifs, l’équation associée admet quand même des solutions dans les entiers négatifs ! En effet, posons $a_1=-5$ et $a_3=-7$. Un petit calcul montre qu’on a bien égalité,
\[ 8 \, = \, (3+\frac1{-5}) (3+\frac1{-7}). \]
Cette solution vient d’ailleurs, comme on pouvait s’y attendre, des deux termes impairs du cycle $-5,-14,-7,-20,-10,-5$.

Épilogue

À part les trajectoires de $-1$ et de $-5$, on connaît encore un autre cycle pour la transformation de Collatz sur les entiers négatifs. C’est la trajectoire de $-17$, qui est de longueur 18 :
\[ \begin{array}{l} & -17 \rightarrow -50 \rightarrow-25 \rightarrow-74 \rightarrow-37 \rightarrow-110 \rightarrow -55 \rightarrow-164\\ & \rightarrow-82 \rightarrow-41 \rightarrow-122 \rightarrow-61 \rightarrow -182 \rightarrow-91 \rightarrow-272 \\ & \rightarrow-136 \rightarrow-68 \rightarrow-34 \rightarrow-17 \rightarrow \ldots \end{array} \]

Dans le volet rouge de cette série, on exclura d’abord les cycles de longueur 18 sur les entiers positifs, avec des arguments analogues à ceux présentés ici pour la longueur 5. Mais à une différence importante près : en longueur 18, il devient presque impossible de connaître la répartition des pairs et des impairs, sa combinatoire devenant ingérable.

Pour surmonter cette difficulté, il faudra faire un petit saut dans l’abstraction, en introduisant une notation spécifique pour distinguer les pairs des impairs dans un cycle hypothétique.

Ce n’est que dans une seconde partie du volet rouge qu’on invoquera les logarithmes et l’approximation rationnelle pour pouvoir exclure, sur les entiers positifs, toutes les longueurs de cycles comprises entre 4 et 17.000.000.000.