196-Algorithm
Lychrelové číslo (anglicky Lychrel number) je přirozené číslo, které nemůže vytvořit palindrom iterací procesu sčítání původního čísla s číslem s obráceným pořadím jeho číslic. Tento proces je nejznámější pod pojmem algoritmus 196 (196-Algorithm), právě podle čísla 196, které je nejmenším číslem v desítkové soustavě, o kterém se předpokládá, že je lychrelovým číslem. Zatím nebylo dokázáno, že takové přirozené číslo z desítkové soustavy existuje. Wade VanLandingham tento jev údajně pojmenoval jako anagram vytvořený ze jména jeho přítelkyně Cheryl.
Proces otočení a přičtení
Jedná se o velmi jednoduchý proces:
- Vybere se číslo
- Otočí se pořadí číslic a vzniklé číslo se sečte s původním číslem
- Pokud součet netvoří palindrom, přejde se zpět k druhému kroku
Například 123 + 321 = 444 nebo 78 + 87 = 165, 165 + 561 = 726, 726 + 627 = 1353, 1353 + 3531 = 4884.
Některá čísla čísla vytvoří palindrom po několika opakováních tohoto procesu, přesněji 80 % přirozených čísel do 10 000 vytvoří palindrom po čtyřech nebo méně krocích a 90 % vytvoří palindrom do sedmi kroků. Ale například 89 vytvoří palindrom (8 813 200 023 188) až po 24 krocích. Nejmenším kandidátem na lychrelové číslo je tedy 196, dále pak následují 295, 394, 493, 592, 689, 691, 790, 879...
Hledání palindromu 196
Jelikož je 196 nejmenší číslo, o kterém se předpokládá, že opakováním výše zmíněného procesu nevytvoří palindrom, byla mu věnována nejvyšší pozornost.
Již v 80. letech 20. století se o tento problém zajímali počítačoví nadšenci. V roce 1985 běžel program Jamese Killmana 28 dní a dosáhl čísla dlouhého 5366 číslic. Od roku 1987 do roku 1990 pak běžel program Johna Wolkera, napsaný v jazyku C, a dosáhl čísla obsahujícího milión číslic bez nalezení palindromu. V hledání dále pokračoval Tim Irvin, který dosáhl hranice dvou milionů číslic. Následoval ho Jason Doucette, Wade VanLandingham a Romain Dolbeau, který dokončil přes bilión iterací a v roce 2012 dosáhl čísla s 600 milióny číslic. Palindrom nebyl dodnes (30. 11. 2016) nalezen.
Reference
V tomto článku byl použit překlad textu z článku Lychrel number na anglické Wikipedii.
Externí odkazy
- "Sloane's A023108 : Positive integers which apparently never result in a palindrome under repeated applications of the function f(x) = x + (x with digits reversed)", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- John Walker – Three years of computing
- Tim Irvin – About two months of computing
- Jason Doucette – World records – 196 Palindrome Quest, Most Delayed Palindromic Number
- Benjamin Despres
- 196 and Other Lychrel Numbers by Wade VanLandingham
- Weisstein, Eric W., "196-Algorithm", MathWorld.
- MathPages – Digit Reversal Sums Leading to Palindromes
- NumberPhile