- 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 anagramme du nom de sa fiancée, Cheryl. Les nombres de Lychrel sont des nombres théoriques. On n'en connait aucun, bien que de nombreux nombres soient suspectés. Le plus petit nombre suspecté d'être de Lychrel est 196.
Sommaire
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[1].
- 1 186 060 307 891 929 990 nécessite 261 itérations pour aboutir à un palindrome de 119 chiffres ce qui constitue le record courant du palindrome le plus retardé. Il a été trouvé par l'algorithme de Jason Doucette le 30 novembre 2005[2].
Nombres de Lychrel potentiels
On remarque que pour certains nombres ce processus ne 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[3],[4]. Ainsi au vu des nombreuses itérations effectuées on conjecture que 196 et tous les nombres ci-dessous sont de Lychrel.
La liste[5] 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[6] Le site de Wade VanLandingham fait la liste du nombre de candidats par nombre de chiffres[7].
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[8]. 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.
A 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 ne l'a pas encore trouvé de nombre de Lychrel.
Les premières graines potentielles sont : 196, 879, 1 997 ...
La recherche de 196
196 étant le plus petit des candidats à être un nombre de Lycrel, 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 toile 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 1 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 atteint un nombre de 2 millions de chiffres en seulement 3 mois sans trouver de palindrome. Jason Doucette poursuivit la lancée et atteint 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 : le magazine des sciences pour enfant au Canada. Le 1er 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). Malgré cela aucun palindrome n'a été trouvé.
Bien sur d'autres candidats comme 879, 1997 et 7059 ont aussi été longuement testés par la même méthode de brute force en atteignant aussi plusieurs millions d'itérations sans trouver le moindre palindrome[9].
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)
- http://www.jasondoucette.com/pal/89
- http://www.jasondoucette.com/pal/
- http://www.math.niu.edu/~rusin/known-math/96/palindrome
- http://www.mathpages.com/home/kmath004.htm
- OEIS
- http://www.p196.org/lychrel%20records.html
- http://www.p196.org/lychrel%20seeds.html
- http://home.cfl.rr.com/p196/math%20solutions.html
- http://home.cfl.rr.com/p196/lychrel+records.html
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
- MathPages - introduction au nombre de Lychrel et preuve d'existence dans d'autres bases
Wikimedia Foundation. 2010.