Nombre de Lychrel

Un nombre de Lychrel est un nombre naturel qui ne peut pas former de nombre palindrome lorsqu'il est soumis au processus itératif qui consiste à l'additionner au nombre formé de l'inversion de ses chiffres en base 10. Le nom « Lychrel » a été inventé par Wade VanLandingham : il s'agit d'une quasi-anagramme du nom de sa fiancée, Cheryl. Les nombres de Lychrel sont des nombres théoriques. On n'en connaît aucun, bien que de nombreux nombres soient suspectés. Le plus petit nombre suspecté d'être de Lychrel est 196.

Définition formelle

Soit n un entier naturel non nul, on a : $n=a_{p}\times 10^{p}+a_{p-1}\times 10^{p-1}+...+a_{1}\times 10+a_{0}=\sum _{i=0}^{p}a_{i}\times 10^{i}$, où chaque $a_{i}$ désigne un chiffre entre 0 et 9 (chiffre des unités, des dizaines, des centaines...) et $a_{p}\neq 0$.

On appelle renversé de n le nombre $n'=a_{0}\times 10^{p}+a_{1}\times 10^{p-1}+...+a_{p-1}\times 10+a_{p}=\sum _{i=0}^{p}a_{p-i}\times 10^{i}$ (la notation $n'$ est ici arbitraire).

Pour tout nombre entier naturel $n_{0}$ non palindrome, c'est-à-dire tel que $n_{0}\neq n'_{0}$, on effectue l'algorithme suivant :

$n_{1}=n_{0}+n'_{0}$

$n_{2}=n_{1}+n_{1}'$

$\dots$

$n_{p}=n_{p-1}+(n_{p-1})'$

$\dots$

On arrête l'itération à la j-ème étape si $n_{j}=n_{j}'$.

Un nombre est dit de Lychrel, si cet arrêt ne survient jamais, c.-à-d. si l'algorithme produit une suite infinie d'entiers non palindromes, ou encore si à chaque étape, $n_{j}\neq n_{j}'$.

Généralisation à des bases entières positives quelconques

Soit n un entier naturel en base B > 1 entière, on a : $n_{B}=a_{p}B^{p}+a_{p-1}B^{p-1}+...+a_{1}B+a_{0}=\sum _{i=0}^{p}a_{i}B^{i}$, où $a_{p}\neq 0$ et $0\leq a_{i}<B$.

On note alors $n'_{B}=a_{0}B^{p}+a_{1}B^{p-1}+...+a_{p-1}B+a_{p}=\sum _{i=0}^{p}a_{p-i}B^{i}$. Suivant le même processus on calcule :

$(n_{B})_{1}=(n_{B})_{0}+(n'_{B})_{0}$

$(n_{B})_{2}=(n_{B})_{1}+(n'_{B})_{1}$

$\dots$

$(n_{B})_{p}=(n_{B})_{p-1}+(n'_{B})_{p-1}$

Un nombre n est dit de Lychrel en base B si l'algorithme produit une suite infinie d'entiers non palindromes en base B, c.-à-d. si à chaque étape, $(n_{B})_{j}\neq (n'_{B})_{j}$.

Processus itératif : inversion et addition

À partir d'un nombre initial en base décimale on crée la somme de ce dernier et de son miroir (c'est-à-dire qu'on permute l'ordre des chiffres). Par exemple pour 124 : on crée 124 + 421 = 545. Si ce nouveau nombre est un palindrome alors le nombre initial n'est pas un nombre de Lychrel. Si ce n'est pas le cas le nombre initial est toujours candidat à être de Lychrel. Puis on recommence avec le dernier nombre créé. On peut remarquer que tous les nombres de un et deux chiffres aboutissent à un palindrome. 80 % des nombres en dessous de 10 000 aboutissent à un palindrome en moins de 4 itérations, et environ 90 % en moins de 7.

Voici quelques exemples de nombres qui ne sont pas de Lychrel :

• 124 nécessite une itération : 124 + 421 = 545
• 59 nécessite 3 itérations :

  59 → 59 + 95 = 154

  154 → 154 + 451 = 605

  605 → 605 + 506 = 1 111

• 89 nécessite 24 itérations.
• 13968441660506503386020 nécessite 289 itérations pour aboutir à un palindrome de 142 chiffres ce qui constitue le record actuel du palindrome le plus retardé. Il a été trouvé par l'algorithme de Anton Stefanov le 4 janvier 2021.

Nombres de Lychrel potentiels

On remarque que pour certains nombres ce processus semblerait ne pas s'arrêter. C'est en particulier le cas pour 196 qui est le plus petit de ces nombres (et ainsi c'est pourquoi on s'y intéresse le plus). Le problème est que l'on n'arrive pas à montrer que pour ces nombres le processus ne s'arrête pas. Du moins cela dépend de la base car pour certaines bases cela est possible. Ainsi au vu des nombreuses itérations effectuées on conjecture que 196 et tous les nombres ci-dessous sont de Lychrel.

La liste des premiers nombres de Lychrel candidats sont : 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1 495, 1 497, 1 585, 1 587, 1 675, 1 677, 1 765, 1 767, 1 855, 1 857, 1 945, 1 947, 1 997… Les programmes de Jason Doucette, Ian Peters et de Benjamin Despres ont trouvé beaucoup d'autres candidats. En effet, le programme de Benjamin Despres a identifié tous les candidats de moins de 17 chiffres. Le site de Wade VanLandingham fait la liste du nombre de candidats par nombre de chiffres.

La méthode par force brute utilisée initialement par John Walker a été réétudiée pour profiter de la particularité du processus. Par exemple, Vaughn Suite a conçu un programme qui ne garde que le premier et le dernier chiffre à chaque itération, il est ainsi possible de vérifier si le nombre (ne) converge (pas) vers un palindrome sans avoir à retenir tout le nombre en mémoire. Mais jusqu'à présent aucun algorithme n'a été développé pour contourner le processus d'inversion et d'addition.

Terminologie des nombres de Lychrel

Diagramme du fil créé par la graine 196. Les nombres surlignés sont les nombres apparentés à 196. Les nombres dans le rectangle sont les nombres du fil.

Le terme de « fil » (thread en anglais) introduit par Jason Doucette correspond à une suite de nombres obtenue par le processus.

Une « graine » (seed en anglais) est le plus petit nombre engendrant un fil ne terminant pas : il s'agit donc d'un sous-ensemble des nombres de Lychrel. Une graine, comme tout nombre de Lychrel, peut être un palindrome. Ainsi à chaque fil il correspond une unique graine.

À une graine on associe ses nombres apparentés (kin en anglais), terme introduit par Koji Yamashita, ce sont des nombres qui vont converger vers le fil de la graine ou qui appartiennent déjà à ce fil. Il s'agit aussi d'un sous-ensemble de nombres de Lychrel. Ainsi une graine et ses nombres apparentés convergent tous sur le même fil.

Il est à noter que ces considérations ne sont que théoriques étant donné qu'on n'a pas encore trouvé de nombre de Lychrel.

Les premières graines potentielles sont : 196, 879, 1 997… Voir suite A063048 de l'OEIS

La recherche de 196

196 étant le plus petit des candidats à être un nombre de Lychrel, c'est donc lui qui a attiré le plus d'attention. John Walker a commencé la recherche le 12 août 1987 sur une plateforme Sun 3/260 avec un programme écrit en C qui effectuait les itérations et qui vérifiait si le nombre était un palindrome. Le programme marchait en tâche de fond avec une faible priorité et produisait un rapport toutes les deux heures en enregistrant le dernier résultat à l'extinction du système. Cela dura presque 3 ans, et finit (comme cela lui était demandé) le 24 mai 1990 avec le message suivant :

Point d'arrêt atteint après 2 415 836 itérations.

Le nombre possède 1 000 000 chiffres.

196 a donc atteint un nombre à un million de chiffres après 2 415 836 itérations sans parvenir à un palindrome. Walker publia ses recherches sur le net avec ce dernier rapport en invitant d'autres personnes à recommencer la recherche en repartant du dernier nombre trouvé. En 1995, Tim Irvin utilisa un superordinateur et atteignit un nombre de 2 millions de chiffres en seulement 3 mois sans trouver de palindrome. Jason Doucette poursuivit la lancée et atteignit 12,5 millions de chiffres en mai 2000. Wade VanLandingham utilisa le programme de Jason Doucette pour atteindre 13 millions de chiffres, un record publié dans Yes Mag, magazine des sciences pour enfants au Canada. Le 1^er mai 2006, VanLandingham atteignit la barre des 300 millions de chiffres (avec une moyenne d'un million de chiffres tous les 5 ou 7 jours). En 2011, Romain Dolbeau utilisa un calcul distribué pour arriver à un milliard d'itérations soit un nombre de 413 930 770 chiffres. En février 2015, ses calculs atteignirent un nombre à un milliard de chiffres. Malgré cela aucun palindrome n'a été trouvé.

Bien sûr d'autres candidats comme 879, 1 997 et 7 059 ont aussi été longuement testés par la même méthode de force brute en atteignant aussi plusieurs millions d'itérations sans trouver le moindre palindrome.

Dans d'autres bases

Les opérations d'inversion des chiffres et de somme n'étant pas propres à la base 10, il est possible de chercher des nombres de Lychrel dans d'autres bases. Ainsi il est prouvé qu'en base 2, le nombre 10110 (22 en base 10) est un nombre de Lychrel. L'existence de nombres de Lychrel a été prouvée lorsque la base est une puissance de 2, ou si elle vaut 11, 17, 20 ou 26.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lychrel number » (voir la liste des auteurs).

Liens externes

• John Walker - Sur les trois années de calculs de John Walker
• Tim Irvin - Environ trois mois de calculs
• Jason Doucette - World records - Sur la recherche de 196 et du palindrome le plus retardé
• Benjamin Despres
• 196 et autres nombres de Lychrel de Wade VanLandingham