Lychrel-számok
A Lychrel-számok olyan természetes számok, melyekből nem nyerhető palindromszám annak a műveletnek az iterációjával, hogy hozzáadjuk a számjegyeinek fordított sorrendben felírásával kapott számot. Ezt a műveletet néha 196-algoritmusnak nevezik, a művelethez kapcsolódó leghíresebb számról. Tízes számrendszerben egyetlen Lychrel-szám létezését sem sikerült matematikailag bizonyítani, de több számról statisztikai és heurisztikus okoskodások alapján gyanítják, hogy Lychrel-számok lehetnek.[1] A „Lychrel” nevet Wade Van Landingham adta ezeknek a számoknak barátnője keresztneve, Cheryl után.
A megfordítási és hozzáadási folyamat szerkesztés
A megfordítási és hozzáadási folyamat egy szám és a számjegyeinek fordított sorrendben való felírásával kapott szám összegét képezi. Például 56 + 65 = 121. Egy másik példa, 125 + 521 = 646.
Néhány szám viszonylag gyorsan, néhány iteráció után palindrom lesz, ezért biztosan nem Lychrel-számok. Az összes egy- és kétjegyű szám végül palindrom lesz a megfordítási és hozzáadási folyamat során.
A 10 000 alatti számok kb. 80%-a palindrom lesz 4 vagy kevesebb lépésben. Kb. 90% palindrom lesz 7 vagy kevesebb lépésben. Néhány további példa:
- Az 56 egyetlen iteráció után palindrom lesz: 56+65 = 121.
- Az 57 két iteráció után: 57+75 = 132, 132+231 = 363.
- Az 59 három iteráció után: 59+95 = 154, 154+451 = 605, 605+506 = 1111
- A 89-nek szokatlanul sok, 24 iteráció kell (a legtöbb a 10 000 alatti számok közül, amikre ismert az algoritmus végeredménye), így éri el a 8 813 200 023 188 számot
- A 10 911 55 lépésben éri el a 28 jegyű 4668731596684224866951378664 palindromot.
- Az 1186060307891929990 261 lépésben éri el a 119 jegyű 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 palindromot, ami a jelenlegi rekord a leghosszabban késleltetett palindromszámra. Jason Doucette algoritmusa és programja segítségével találták, felhasználva megfordítási és hozzáadási kódját 2005. november 30-án.
A legkisebb szám, amiről nem tudni, hogy végül palindrom számhoz jut vele az algoritmus, a 196. Más megfogalmazásban, a 196 a legkisebb Lychrel-számjelölt.
A Lychrel-szám jegyeinek megfordításával kapott szám is Lychrel-szám.
Bizonyítás hiánya szerkesztés
Az a sejtés, hogy a 196 és a többi szám, aminek nem sikerült megtalálni az algoritmus leállási pontját mind Lychrel-számok, de tízes számrendszerben ezt egyikről sem sikerült igazolni. Az ilyen számokat informálisan „Lychrel-jelölt” számoknak nevezik. Az első néhány Lychrel-jelölt:
- 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997. (A023108 sorozat az OEIS-ben)
A félkövér számok gyanítottan Lychrel-„mag”-számok (lásd lejjebb). Jason Doucette, Ian Peters és Benjamin Despres programjaival egyéb Lychrel-jelölt számokat is találtak. Sőt, Benjamin Despres szoftvere azonosította az összes, 17 számjegynél rövidebb Lychrel-magszám-jelölteket is.[2] Wade VanLandingham weboldala listázza az egyes számjegyhosszakhoz tartozó Lychrel-magszám-jelöltek számát.[3]
A John Walker által eredetileg használt brute-force módszert később finomították, hogy jobban kihasználja az iteráció speciális tulajdonságait. Például Vaughn Suite programja minden iterációnak csak az első és utolsó pár számjegyét menti el, ami lehetővé teszi több millió iteráció tesztelését anélkül, hogy az egész iterációt fájlba kellene lementeni.[4] Olyan algoritmust azonban még nem sikerült találni, ami magát a megfordítva hozzáadás folyamatát kiküszöbölhetővé tenné.
Szálak, magok és rokonok (thread, seed and kin numbers) szerkesztés
A Jason Doucette által megalkotott szál (thread) kifejezés számok egy-egy sorozatára utal, melyek végül vagy eljutnak egy palindromszámhoz, vagy nem. Bármely mag (seed) és a hozzá tartozó rokon (kin) számok ugyanazon a szálon találhatók.
A mag (seed) számok a Lychrel-számok részhalmaza, egy olyan szál legkisebb eleme, ami végül nem jut el palindromhoz. A magszám maga is lehet palindrom. Az első három feltételezett példa a fenti listában félkövérrel van kiemelve.
A rokon (kin) számok a Lychrel-számok részhalmaza, a szál minden elemét tartalmazza a magon kívül; a kifejezést Koji Yamashita alkotta meg 1997-ben.
196-palindromkeresés szerkesztés
Mivel tízes számrendszerben a 196 a legkisebb Lychrel-számjelölt, erre a számra irányult a legnagyobb figyelem.
Az 1980-as években a 196-palindromprobléma fölkeltette a mikroszámítógép-rajongók érdeklődését, Jim Butterfield és mások a nagyközönségnek szánt magazinokban megjelent keresőprogramjaival.[5][6][7] 1985-ben James Killman programja dolgavégezetlenül futott több mint 28 napig, 12 954 menet után egy 5366 jegyű számot elérve.[7]
John Walker 1987. augusztus 12-én kezdte meg a keresést egy Sun 3/260 munkaállomáson. Az általa írt C nyelvű program az iterációk elvégzésén túl képes volt a háttérben futni alacsony prioritással, 2 óránként, illetve a rendszer leállításakor pillanatképet menteni az addigi haladásról, majd a rendszer újraindulásakor automatikusan elindulni. 1990. május 24-én állt le a program, amikor 2 415 836 menet után a szám elérte az egymillió számjegy hosszúságot anélkül, hogy palindrommá vált volna. Walker publikálta eredményét az interneten, arra biztatva másokat, hogy innen kiindulva folytassák a keresést.
1995-ben Tim Irvin egy szuperszámítógép számítási kapacitását felhasználva mindössze három hónap alatt elérte a kétmillió számjegyet palindrom elérése nélkül. Jason Doucette folytatta, aki 2000 májusában érte el a 12,5 millió számjegyet. Wade VanLandingham Jason Doucette programját felhasználva érte el a 13 millió számjegyet, amit aztán a kanadai gyerekek tudományos magazinjában, a Yes Magben publikált. 2000 júniusa óta Wade VanLandingham vitte tovább a zászlót különböző lelkes amatőrök által írt programok segítségével. 2006. május 1-jére érte el a 300 millió számjegyet (5-7 naponta 1 millió számjegyet haladva előre). Elosztott számítástechnika használatával[8] Romain Dolbeau 2011-re egymilliárd iterációval végzett ekkor egy 413 930 770 jegyű számnál tartva, 2012 júliusában pedig 600 millió számjegynél jártak a számítások.[9] Palindromot azóta sem találtak.
Más Lychrel-számjelölteket is megpróbáltak brute force módszerrel megvizsgálni, köztük a 879, 1997 és 7059 számokat több millió iteráción keresztül nem sikerült palindrom számig eljuttatni az algoritmussal.[10]
Más számrendszerekben szerkesztés
A kettes számrendszerben a 10110 (decimális 22) bizonyítottan Lychrel-szám, mivel 4 lépés után 10110100-ig jut, 8 lépés után 1011101000-ig, 12 lépés után 101111010000-hoz jut, és általában véve 4n lépés után egy olyan szám következik, ami 10-val kezdődik, n+1 darab 1-essel, 01-gyel, majd n+1 darab nullával folytatódik. Ez nyilvánvalóan nem palindrom, és bizonyíthatóan a sorozat többi eleme sem az. Eddig főleg kettőhatvány alapú számrendszerekben sikerült bizonyíthatóan Lychrel-számokat találni. A 2, 4, 11, 16, 17, 22 alapoknál egyes számokról sikerült igazolni, hogy sosem jut el az algoritmus palindromszámhoz,[11][12] de a tízes számrendszerben nem sikerült ilyet bizonyítani egyik számról sem.
A legkisebb Lychrel-jelöltek számrendszerenként (A060382 sorozat az OEIS-ben):
| b | A legkisebb lehetséges Lychrel-szám a b számrendszerben b-ben leírva (10-esben) |
|---|---|
| 2 | 10110 (22) |
| 3 | 10201 (100) |
| 4 | 3333 (255) |
| 5 | 10313 (708) |
| 6 | 4555 (1079) |
| 7 | 10513 (2656) |
| 8 | 1775 (1021) |
| 9 | 728 (593) |
| 10 | 196 (196) |
| 11 | 83A (1011) |
| 12 | 179 (237) |
| 13 | CCC (2196) |
| 14 | 1BB (361) |
| 15 | 1EC (447) |
| 16 | 19D (413) |
| 17 | B6G (3297) |
| 18 | 1AF (519) |
| 19 | HI (341) |
| 20 | IJ (379) |
| 21 | 1CI (711) |
| 22 | KL (461) |
| 23 | LM (505) |
| 24 | MN (551) |
| 25 | 1FM (1022) |
| 26 | OP (649) |
| 27 | PQ (701) |
| 28 | QR (755) |
| 29 | RS (811) |
| 30 | ST (869) |
Jegyzetek szerkesztés
- ↑ O'Bryant, Kevin: Reply to Status of the 196 conjecture?'. Math Overflow , 2012. december 26.
- ↑ VanLandingham, Wade: Lychrel Records. p196.org . [2016. április 28-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
- ↑ VanLandingham, Wade: Identified Seeds. p196.org . [2016. április 28-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
- ↑ On Non-Brute Force Methods. [2006. október 15-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
- ↑ (1984) „Bits and Pieces”. The Transactor 4 (6), 16–23. o, Kiadó: Transactor Publishing. (Hozzáférés: 2014. december 26.)
- ↑ Rupert, Dale (1984. október 1.). „Commodares: Programming Challenges”. Ahoy!, 23, 97–98. o, Kiadó: Ion International.
- ↑ a b Rupert, Dale (1985. június 1.). „Commodares: Programming Challenges”. Ahoy!, 81–84,114. o, Kiadó: Ion International.
- ↑ (2014. június 23.) „The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest”. International Supercomputing Conference. [2015. április 19-i dátummal az eredetiből archiválva]. Hozzáférés: 2016. április 30.
- ↑ Dolbeau, Romain: The p196_mpi page. www.dolbeau.name . [2015. február 11-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
- ↑ Archivált másolat. [2006. október 21-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
- ↑ Brown, Kevin: Digit Reversal Sums Leading to Palindromes. MathPages
- ↑ Digit Reversal Sums Leading to Palindromes. [2013. május 30-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 30.)
További információk szerkesztés
- 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)
- 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 (angol nyelven). Wolfram MathWorld
- MathPages – Digit Reversal Sums Leading to Palindromes
- NumberPhile