Vous pouvez retrouver cette question au format pdf.

Question du jeudi #43 : Le mathématicien anglais J.H. Conway a inventé une variante de la suite de Fibonacci, qu'il appelle Subprime Fibs. Partons de deux nombres strictement positifs. Ensuite, on complète la suite petit à petit suivant la règle suivante. Formons la somme des deux derniers termes de la suite : si le résultat est premier, reportons-le tel quel ; s'il ne l'est pas, divisons-le par son plus petit facteur premier et reportons le résultat. Question.

Ainsi, en partant comme dans la suite de Fibonacci des nombres $1$ et $1$, on obtient successivement $2 = 1 +1$ (qui est bien premier), $3 = 2 + 1$, $5 = 2 + 3$ (idem), puis $4 = \frac{5+3}2$, $3 = \frac{5 + 4}{3}$, etc. Les premiers termes de la suite sont les suivants :

où le cycle de 18 nombres en rouge se répète infiniment.

Conway conjecture que quels que soient les deux nombres de départ, la suite finira soit par devenir constante, soit par entrer dans l'un des six cycles qu'il a identifés (en plus de notre cycle de longueur 18, il y en a de longueur 10, 11, 19, 56 et 136).

L'objectif de cette question est plus modeste : montrer qu'il n'existe pas de cycles de longueur 2 ou 3.

1. S'il y avait un cycle d'ordre $2$, c'est-à-dire si l'on pouvait trouver une suite $a, b, a, b, \ldots$ obéissant aux règles Subprime Fibs, on devrait obtenir $a$ en considérant la somme $a+b$ et, le cas échéant, en la divisant par son petit facteur premier. De même, on devrait obtenir $a$ en appliquant le même procédé à la somme $b+a$. Comme $a+b = b+a$, ces deux calculs donneraient évidemment le même résultat, ce qui contredit l'hypothèse $a \neq b$.
2. Le raisonnement est un peu plus compliqué pour le cas d'un cycle de longueur $3$. Supposons donc qu'une suite $a, b, c, a, b, c, \ldots$ obéisse aux règles Subprime Fibs, avec $a$, $b$ et $c$ non confondus. Tirons-en petit à petit des conclusions :

    

   Si en revanche, si c'est $c$ qui est pair, le même raisonnement montre essentiellement que $c=2b$ et $a=3c$. Le cycle est alors \[ 3, 1, 2, 3, 1, 2, \ldots\] ce qui entraîne la même contradiction.

   • Déjà, les trois nombres sont tous différents. En effet, si deux d'entre eux étaient les mêmes (disons $x$), il serait possible de les trouver côte à côte dans la suite, et comme $x+x$ est pair, la suite vaudrait alors à partir de ce moment
   \[ x, x, \frac{x+x}2 = x, \frac{x+x}2 = x, \ldots\] ce qui contredit le fait que le cycle est de longueur $3$. Sans perte de généralité, on peut supposer que $a$ est strictement plus grand que les deux autres.
   • En particulier, $b < a+c$ et $c < a+b$. Pour obtenir $b$ (resp. $c$), il a donc fallu diviser la somme $a+c$ (resp. $a+b$) par son plus petit facteur premier $p$ (resp. $q$). En particulier, on a
   \[ b = \frac{a+c}p \qquad \text{et} \qquad c = \frac{a+b}q.\]
   • Inversement, si $\ell$ est un nombre premier, on a $\frac{b+c}\ell \leq \frac{b+c}2 \leq \max(b,c) < a$. Donc on n'a pas pu diviser $b+c$ par un nombre premier pour obtenir $a$. C'est donc que $a = b+c$ et que $a$ est lui-même premier. Puisqu'il ne peut pas valoir $2$ (cela entraînerait $b = c = 1$, alors qu'on a vu que les trois nombres doivent être différents), il s'agit d'un premier impair. En remplaçant $a$ par $b+c$ dans les formules données plus haut pour $b$ et $c$, on obtient par ailleurs
   \[ (p-1)b=2c \qquad \text{et} \qquad (q-1)c=2b.\]
   • Puisque $a = b +c$ est impair, $b$ et $c$ n'ont pas la même parité. Supposons dans un premier temps que $b$ est pair. Cela entraîne que $pb = a + c$ est pair : son plus petit facteur premier était donc $p = 2$. Ainsi, l'équation précédente devient $b = 2c$, d'où l'on déduit $a = 3c$. Comme $a$ est premier, $c = 1$ et le cycle doit donc être
   \[ 3, 2, 1, 3, 2, 1, \ldots\] Or, cela est absurde : après $3$ et $2$, la règle Subprime Fibs implique que l'on doit écrire $5$, qui est premier. On est donc arrivé à une contradiction.
On a donc bien montré qu'il n'y avait aucun cycle de longueur $3$.

Remarque. Pour démontrer la conjecture de Conway (comme pour la conjecture de Syracuse, avec qui elle partage un certain nombre de caractéristiques), il faudrait pouvoir démontrer deux résultats :

• Que quels que soient les nombres de départ, la suite reste bornée. En particulier, cela entraînerait que toute suite finit par rentrer dans un cycle.
• Qu'il n'y a pas de cycle autre que ceux que l'on a identifiés (les six cycles de longueur $10$, $11$, $18$, $19$, $56$, $136$ et les cycles triviaux où le même nombre se répète à l'infini).

D'une certaine façon, la question que nous venons de résoudre est un (tout petit) pas en direction de ce deuxième point. Richard Guy, Tanya Khovanova et Julian Salazar ont en fait démontré qu'ils n'y avait aucun cycle (non trivial) de longueur $\leq 9$, et qu'il n'y avait qu'un cycle de longueur $10$.

Pour des renseignements supplémentaires sur des questions connexes concernant la conjecture de Syracuse, nous recommandons chaudement l'excellente série d'articles de Shahom Eliahou sur le site Images des Mathématiques :

• Le problème $3n+1$ : élémentaire mais redoutable
• Le problème $3n+1$ : cycles de longueur $5$
• Le problème $3n+1$ : y a-t-il des cycles non triviaux ?

La vignette illustrant cet article est une photographie de John Conway, tirée de la notice wikipédia le concernant.