Pierre Legrand [1]

L’algorithme de la « preuve par 9 » peut être décrit comme suit : on part d’un entier naturel non nul $x_0$, on le remplace par la somme $x_1$ de ses chiffres, puis le nombre $x_1$ obtenu par la somme $x_2$ de ses chiffres et ainsi de suite, jusqu’au moment où l’on atteint un nombre compris entre 1 et 9, qui est le reste de la division de $x_0$ par 9 (sauf quand $x_0$ est multiple de 9, où on obtient 9).

On peut alors se demander ce qu’il advient de ce processus si, au lieu de prendre à chaque étape la somme des chiffres, on prend la somme de leurs carrés.

Ce dernier problème figure dans l’excellent livre de Hugo Steinhaus, « One Hundred Problems In Elementary Mathematics », qui date des années 60, mais pourrait avoir une origine plus ancienne. Il me semble abordable en terminale et, pour la partie expérimentation numérique sur ordinateur, en première.

Étant donné un entier x strictement positif, on appellera s(x) la somme des carrés des chiffres de son écriture décimale. Une valeur de départ $x_0$ étant fixée, on se propose d’étudier la suite définie par la relation de récurrence $x_{n+1} = s(x_n)$.

0. Expérimentation numérique

On voit sans peine, sur des exemples traités à la main ou à la machine (la suite est aisément programmable), que selon toute apparence deux cas seulement sont possibles :

Cas A : la suite se stabilise au bout d’un certain temps à la valeur 1 ;

Cas B : à partir d’un certain rang, la suite est périodique et conforme au schéma

$$4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4 \to ...$$

Il reste à en apporter la preuve.

1. Préalable : Pour tout $x \ge 100$, on a $s(x) < x$.

1.1. Supposons $100 \le < 1 000$.

Alors $s(x)$ est majoré par 3 × 9² = 243, ce qui prouve le résultat pour x > 243.
Pour tout $x \in [100,243]$, on a $s(x) \le 163$, car si x < 200 on a $s(x) \e 1 + 9^2 + 9^2$ et si $200 \le x \le 243$, on a $s(x) \le 4 + 4^2 + 9^2 < 163$. L’inégalité $s(x) < x$ reste donc à prouver seulement sur [100,163]. Or si x = 159, alors s(x)=1 + 25 + 81 = 107 et si $100 \le x \le 16$ avec $x \ne 159$, alors $s(x) \le 1 + 5^2 + 8^2 < 100$.

1.2. Supposons $1 000 \le x < 10 000$.
Alors $s(x) \le 4 \times 92 < 999 < x$.

1.3. Plus généralement, supposons $10^{r-1} \le x < 10^r$.

Il vient $s(x) \le r \times 9^2$. Reste à prouver que $r \times 9^2 < 10^{r-1}$ pour tout $r \ge 4$, ce qui est immédiat par récurrence : en passant d’une valeur à la suivante, on ajoute 81 au premier membre, alors que le second, qui est au moins égal à 1 000, est multiplié par 10.
Notons que, pour x = 99, on a en revanche $s(x)>x$.

2. Quel que soit $x_0$, la suite est bornée.

2.1. L’un au moins des $x_n$ est strictement inférieur à 100.

Supposons que, pour tout n, on ait $x_n \ge 100$ ; d’après ce qui précède, $s(x_n) < x_n$. Nous sommes donc en présence d’une suite infinie strictement décroissante d’entiers naturels, ce qui est absurde (c’est la descente infinie de Fermat).

2.2. On peut donc toujours supposer que $ 1 \le x_0 \le 99$ .

Il suffit pour cela de supprimer éventuellement les premiers termes de la suite, ce qui ne fait que décaler les indices.

2.3. À partir d’un certain rang, on a, pour tout n, $x_n \le 162$.

Nous avons vu en 1.3. que si $100 \le x \le 163$, on a $s(x) < x$. Et si $x < 100$, alors $s(x)$ est majoré par $2 \times 9^2 = 162$. L’intervalle [1,162] est donc stable par s. Puisque l’un des $x_n$ est inférieur à 100, tous les suivants seront donc dans [1,162].

3. Le point de vue du fanatique de l’ordinateur

3.1. Un calcul facile à programmer.

Puisque nous connaissons le résultat à établir et que le comportement de la suite peut être étudié en se limitant à $x_0 \le 99$, le problème est réglé pour quiconque sait bâtir un algorithme. Vérifier que l’on est toujours en présence des cas A ou B décrits au début de cet article est une affaire élémentaire de programmation.

On notera que l’on dispose d’un bon test d’arrêt : stopper le calcul dès que la suite prend une valeur déjà prise. Ou mieux le stopper lorsqu’elle prend l’une des valeurs 1 (ce qui donne le cas A) ou 4 (ce qui donne le cas B).

3 . 2 . Travail à la main et travail à la machine.

Nous avons dû préparer le travail de l’ordinateur en limitant les valeurs initiales à 99 d’entre elles. Ce préalable « manuel » était hélas indispensable. Il s’agit là d’une procédure devenue classique en arithmétique : on démontre qu’un résultat est établi si on le prouve pour une certaine liste finie de cas et on liquide ensuite ces cas par un programme ad hoc.

3.3. Une cause d’insatisfaction.

Pourquoi diable cette suite est-elle périodique à partir d’un certain rang ? Avec l’aide de la machine et par épuisement des cas, nous avons prouvé qu’elle l’est. Mais quelle en est la raison profonde ? Et le résultat serait-il conservé si l’on remplaçait par exemple la somme des carrés des chiffres par la somme de leurs cubes ?

4. Le point de vue du bricoleur rétro

4.1. La suite est périodique à partir d’un certain rang.

Le raisonnement est enfantin. À partir d’un certain indice $n_0$, tous les $x_n$ sont majorés par 162. On a donc une infinité de termes ne pouvant prendre que 162 valeurs distinctes (c’est le principe des tiroirs de Dirichlet : si on répartit plus de k objets dans k tiroirs, il y aura forcément un tiroir contenant au moins deux objets). Il existe donc m et q tels que $x_{m+q} = x_m$ ; d’où par récurrence la périodicité.

4.2. Si la suite est constante à partir d’un certain rang, sa valeur finale est 1.

Il est immédiat que la suite est constante à partir d’un certain rang si et seulement si il existe un rang n tel que $x_{n+1} = x_n$.

Cherchons les x vérifiant l’équation (E) :
$s(x) = x$.

Nous avons vu au tout début de l’étude que, pour tout $x \ge 100$, on a $s(x) < x$.
On est donc ramené au cas où $x \le 99$, donc à discuter l’équation $10u + v = u^2 + v^2$, soit $u (10 - u) = v (v - 1)$, avec u et v entiers de 0 à 9. Le premier membre prend les valeurs 0, 9, 16, 21, 24, 25 et le second membre les valeurs 0, 2, 6, 12, 20, 30, 42, 56, 72.
La seule solution est donc u = 0, c’est-à-dire x = 1.

4.3. Que se passe-t-il si la suite n’est pas constante à partir d’un
certain rang ?

C’est là évidemment que le bricoleur rétro commence à regretter de ne rien avoir appris de la computer science. Il ne lui reste plus qu’à faire tristement les choses à la main. Après tout, il n’y a « que » 99 suites à étudier, de $x_0 = 1$ à $x_0 = 99$.

Heureusement, il a entendu parler des méthodes de crible et n’oublie pas les remarques de symétrie. Il se limite donc, puisque $s(10v + u) = s(10u + v)$, aux nombres $10u + v$, avec $0 \le u \le v \le 9$, dont il fait un tableau triangulaire. Puis il barre un nombre en rouge si la suite issue de ce nombre prend la valeur 1, en bleu si elle prend la valeur 4. Ainsi, partant de $x_0 = 47$, il obtient une séquence du type B :

$$47 \to 56 \to 16 \to 37 \to 58 \to 89 \to 24 \to 2 \to 4$$

ce qui lui permet de barrer en bleu les nombres 47, 56, 16, 37, 58, 89, 24, 2 et 4 . Il continue ainsi patiemment en n’oubliant pas que si, dans une séquence bâtie à partir d’une nouvelle valeur de $x_0$, on tombe sur un nombre déjà barré, tous les nombres inférieurs à 100 de cette séquence sont à barrer, ainsi que ceux que l’on obtient en permutant leurs deux chiffres. Au terme de ce travail fastidieux, mais assez rapide, il constate que tous les nombres ont été barrés.

N’étant ni tellement informaticien ni tellement bricoleur, nous laisserons au lecteur le soin de vérifier par le procédé de son choix que le résultat annoncé est correct : les cas A et B sont bien les seuls possibles.

5. Généralisation

Si, au lieu de $s(x)$, on considère $s_k(x)$, somme des puissances k-ièmes des chiffres de l’écriture décimale de x, où k est un entier strictement positif, on peut étudier de la même façon le comportement de la suite définie à partir d’un entier naturel $x_0$ par la formule $x_{n+1} = s_k(x_n)$. La démarche est la même que lorsque k = 2. Donnons-en les grandes lignes.

5.1. Pour tout x assez grand, $s_k(x) < x$.

Supposons $10^{r-1} \le x < 10^r$ ; x a r chiffres, donc $s_k(x) \le r 9^k$. Il suffira d’avoir $r 9^k < 10^{r-1}$, c’est-à-dire $r - \log r > 1 + k \log 9$ (log désignant le logarithme décimal), pour assurer $s_k(x) < x$. Le premier membre de l’inégalité est une fonction croissante de r, de limite +$\infty$. Il existe donc $\alpha_k$ tel que, pour tout $r \ge \alpha_k, r 9^k < 10^{r-1}$. Il en résulte que, pour tout $x \ge 10^{\alpha_{k}-1}, s_k(x) < x$.

5.2. Le segment $J_k = [0,10^{\alpha_k-1}]$ est stable par la fonction $s_k$.

Soit $x \in J_k$ ; x a au plus $\alpha_k$ chiffres, donc $s_k(x) \le \alpha_{k} 9^k < 10^{\alpha_{k}-1}$.

5.3. Quel que soit $x_0$, tous les $x_n$ sont dans $J_k$ à partir d’un certain rang.

Si aucun $x_n$ n’était dans $J_k$, on aurait, pour tout n, $x_{n+1} < x_n$ et la descente infinie mènerait à une contradiction. Il existe donc m tel que $x_m \in J_k$ ; tous les termes suivants sont aussi dans $J_k$, puisque ce segment est stable par $s_k$.

5.4. La suite est périodique à partir d’un certain rang.

Cette suite infinie ($x_n$) ne peut d’après ce qui précède prendre qu’un nombre fini de valeurs. Le principe des tiroirs permet alors de conclure comme en 4.1.
Hélas, pour $k \ge 3$, les résultats n’ont pas en général la belle simplicité qu’ils ont pour k = 1 et k = 2 : l’aspect des suites est beaucoup plus divers. Cependant le cas k = 3 présente des particularités assez imprévues.

6. Quelques indications pour k = 3.

6.1. Pour tout x, $s_3(x) \equiv x$ (mod 3).

La valeur modulo 3 de x est celle de la somme de ses chiffres. Mais, pour tout entier u, on a $u^3 \equiv u$ (mod 3), car, dans le produit u (u − 1) (u + 1), un des trois facteurs est multiple de 3. La somme des chiffres de x a donc même valeur modulo 3 que la somme de leurs cubes.

Conséquence : quel que soit $x_0$, tous les $x_n$ ont même valeur modulo 3 que $x_0$. Cela permet de classer les suites en trois catégories dont, on le verra, les comportements sont différents.

6 . 2 . Tous les $x_n$ sont, à partir d’un certain rang, dans le segment [ 0 ,2 188].

Ce segment (on observera que $2 188 = 1 + 3 \times 93$) est stable par $s_3$, la démonstration étant du même type que celles faites en 5.2. et 5.3. On montre en outre aisément que c’est le plus petit segment du type [0,A] qui ait cette propriété de stabilité.

6.3. Les résultats.

On n’a à étudier le comportement de la suite « que » pour 2 188 valeurs de$ x_0$. Si le calcul à la main devient ici un martyre, la situation peut être aisément réglée par un programme ad hoc. L’ordinateur est idiot, mais il est infiniment patient, sûr et rapide.
Voici ce qu’on obtient :
Si $x_0 \equiv 0$ (mod 3), alors la suite se stabilise à la valeur 153.
Si $x_0 \equiv -1$ (mod 3), alors la suite se stabilise à l’une des valeurs 371 ou 407.
Si $x_0 \equiv 1$ (mod 3), alors :

• ou la suite se stabilise à l’une des valeurs 1 ou 370 ;
• ou la suite est périodique à partir d’un certain rang, selon l’un des quatre modèles

  $$136 \to 244 \to 136$$

  $$919 \to 1459 \to 919 $$

  $$ 55 \to 250 \to 133 \to 55 $$

  $$160 \to 217 \to 352 \to 160$$

N.B. : Le lecteur masochiste pourra vérifier que, pour k = 4, il existe des suites ($x_n$) se stabilisant aux valeurs 1, 1634, 8202, 9474 et que ce sont les seules valeurs finales possibles.
Il pourra aussi vérifier que, pour k = 2 mais avec une base autre que dix, les résultats peuvent être nettement moins agréables qu’en base dix (essayer par exemple la base 5 ou pire la base 7).

Conclusion

Bien que le problème traité ici n’ait en lui-même qu’un intérêt de curiosité, il nous a permis de mettre en oeuvre quelques-unes des idées clés de l’arithmétique. Il montre en outre comment on peut utiliser l’ordinateur comme auxiliaire de la démonstration :
une fois que le raisonnement a borné le nombre de cas à étudier, on confie à la machine l’exploration de ces cas.

Pour des élèves de terminale, cette étude me semble avoir le mérite de présenter, à partir de suites dont le comportement inattendu peut piquer la curiosité, des raisonnements à la fois accessibles et inhabituels à ce niveau. Mais peut-être suis-je trop optimiste…

Le fait qu’un mathématicien de génie comme Steinhaus s’y soit intéressé donne d’ailleurs à réfléchir. Nous aurions tort de mépriser les récréations mathématiques : elles sont souvent plus formatrices et plus profondes qu’il n’y paraît. Pour donner un exemple entre mille, n’est-ce pas d’un divertissement d’Euler, les ponts de Koenigsberg, qu’est née la théorie des graphes ?

Annexe [2] : exploration au tableur pour la somme des carrés

La seule difficulté consiste à trouver la formule de la fonction s.
L’étude ci-dessus montre qu’on peut se limiter aux nombres de trois chiffres.
Si x = 100 u + 10 v + w, alors

• w est le reste de la division de x par 10, le quotient q étant 10 u + v ;
• v est le reste de la division de q par 10 ;
• u est le quotient de la division de x par 100 (ou bien de q par 10).

En langage Excel : w = mod(x ;10) ; v = mod(quotient(x ;10) ;10) ; u = quotient(x ;100).
Il suffit donc de

• placer dans la colonne 1 les entiers de 1 à 99 ;
• écrire dans la cellule B1 la formule :

=MOD(A1 ;10)^2+MOD(QUOTIENT(A1 ;10) ;10)^2+QUOTIENT(A1 ;100)^2

• recopier cette formule jusqu’à la ligne 99 ;
• recopier la colonne B à droite aussi loin que possible.
  Une mise en forme conditionnelle de l’ensemble des cellules (par exemple rouge quand le contenu de la cellule est le nombre 1, bleu quand c’est le nombre 4) met en évidence les deux types de suites.

<redacteur|auteur=500>