Problém 196

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. října 2019; kontroly vyžadují 44 úprav .

Problém čísla 196  je podmíněným názvem nevyřešeného matematického problému : není známo, zda operace „převrátit a přidat“ aplikovaná na číslo 196 v určitém počtu případů povede k palindromu .

Lychrelovo číslo je přirozené  číslo , které se nemůže stát palindromem pomocí iterativního procesu „převrátit a přidat“ v desítkovém zápisu. Tento proces se nazývá 196 algoritmus . Jméno Lychrel, které vymyslel Wade VanLandingham , je nepřesnou anagramem jména jeho přítelkyně Cheryl . Neexistují žádná přísně dokázaná Lichrelova čísla (pro desítkovou číselnou soustavu; existují dokázaná Lichrelova čísla pro některé jiné číselné soustavy), ale u mnoha čísel se předpokládá, že tomu tak je, přičemž nejmenší je 196 .   

Překlopte a složte

Operace „ Reverse-and-add “  spočívá v přidání původního čísla s jeho „obrácenou“ kopií, tedy číslem, jehož číslice jsou zapsány v obráceném pořadí. Například 56 + 65 = 121, 521 + 125 = 646.

Tuto operaci lze aplikovat na libovolné přirozené číslo. Pokud v důsledku aplikace této operace Nkrát na určité číslo získáme palindrom , pak se takové číslo nazývá "odložený palindrom" , rozdělený v N iteracích. Na rozdíl od zpožděných palindromů u Lishrelových čísel tato operace nevede k palindromu, bez ohledu na to, kolikrát ji provedeme.

Některá čísla (zejména všechna jednociferná a téměř všechna dvouciferná) se stanou palindromy poměrně rychle - po provedení několika operací. Takže asi 80 % všech čísel menších než 10 000 se vyřeší na palindrom ve 4 nebo méně iteracích. Asi 91 % – v 7 nebo méně iteracích. A pouze dvě čísla - 89 a 98 - vyžadují neobvykle velké množství: 24 operací.

Zde je několik příkladů opožděných palindromů:

Nejmenší číslo, počínaje 1 , které zřejmě netvoří palindrom, je trojciferné číslo 196 . Toto je nejmenší známé Lichrelovo potenciální desetinné číslo.

Nejvíce opožděné palindromy

Mezi nekonečným počtem zpožděných palindromů jsou zvláště zajímavá čísla, která vyžadují největší počet iterací, aby se z nich stal palindrom.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ.  Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Toto číslo drželo světový rekord pro nejvíce zpožděné palindromy více než 13 let.

V květnu 2017 televizní kanál MIR24 uvedl, že moskevský školák Andrey Shchebetov objevil největší známý zpožděný palindrom, číslo 1999291987030606810 . Na tomto čísle však není nic zajímavého, protože je získáno jednoduchou permutací dvojic symetrických číslic z čísla objeveného Jasonem Doucettem. Největší známé 19místné číslo, které lze rozlišit ve 261 iteracích, je 1 999 999 936 042 548 910 a největší známé číslo má 35 číslic .

26. dubna 2019 vytvořil Rob van Nobelen (Nizozemec . Rob van Nobelen ) nový světový rekord pro nejvíce zpožděné palindromy: 23místné číslo 12 000 700 000 025 339 936 491 , které se za 288 kroků změní na palindrom.

5. ledna 2021 Anton Stefanov publikoval [1] 23místná čísla 13,968,441,660,506,503,386,020 a 13,568,441,660,506,503,386,420 , která se proměnila ve stejný počet nalezených 28 palinových kroků jako Rob. 14. října 2021 Dmitrij Maslov oznámil [2] , že našel menší 23místné číslo, které se vyřeší ve 289 iteracích: 10 036 069 400 174 999 499 950 .

Dmitrij Maslov vytvořil 14. prosince 2021 [3] nový světový rekord mezi nejvíce zpožděnými palindromy: 25místné číslo 1000206827388999999095750 , které se po 293 iteracích stává 132místným palindromem. Toto číslo je aktuálním světovým rekordem pro nejvíce zpožděné palindromy.

Sekvence OEIS A326414 obsahuje 19353600 čísel, která se po 288 krocích změní na palindrom.

Sekvence A281506 obsahuje seznam 108864 zpožděných palindromů, které vyžadují 261 iterací, aby se staly palindromem. Začíná na 1186060307891929990 a končí na 1999291987030606810 .

Vysvětlení vzorce

Řekněme, že je to přirozené číslo. Funkci Lichrel definujeme pro základní čísla (viz související definice) takto:

kde je počet číslic v základním čísle a

hodnotu každé číslice čísla. Číslo je Lichrelovo číslo , pokud neexistuje žádné přirozené číslo takové, že , kde je iterace

Nový problém

V jiných číselných systémech , některá čísla mohou být dokázaná nikdy tvořit palindrom po postupných iteracích [4] [5] , ale žádný takový důkaz byl najitý pro 196 a jiná desetinná čísla.

Existuje domněnka , že 196 a další čísla, která se ještě nestala palindromem, jsou čísla Lishrel, ale pro žádné číslo neexistuje žádný přesný důkaz, že tomu tak je. Taková čísla jsou neformálně označována jako „kandidáti na čísla Lichrel“. Prvních několik kandidátů na čísla Lychrel je sekvence A023108 v OEIS :

196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1797 7 1845 .

Čísla vytištěná tučně jsou považována za základní čísla Lychrel (viz níže ). Počítačové programy Jasona Doucetta, Jana Peterse a Benjamina Desprese našly další kandidáty na Lishrel. Benjamin Despres navíc identifikoval všechna základní Lichrelova čísla s méně než 17 číslicemi [6] . Web Wade VanLandingham obsahuje seznamy základních čísel Lychrel pro každou délku čísel. [7]

Metoda hrubé síly , původně vyvinutá Johnem Walkerem, byla vylepšena, aby využívala výhody iteračního chování. Existuje například program vytvořený Won Suite, který ukládá pouze prvních a posledních několik číslic každé iterace, což vám umožňuje testovat digitální vzory v milionech iterací, aniž byste museli každou iteraci ukládat do souboru [8] . Ale zatím nebyl vynalezen žádný algoritmus , který by obcházel iterační proces.

Související definice

Termín vlákno nebo vlákno ( anglicky  vlákno ) vynalezl Jason Doucette, označující posloupnost čísel získaných v důsledku opakování původního čísla. Základní číslo ( eng.  seed ) a související související ( eng.  kin ) čísla se sbíhají v jednom proudu. Proud nezahrnuje původní základní číslo ani jeho relativní , ale pouze čísla, která jsou oběma společná poté, co se sblíží.

Základní čísla jsou podsekvencí Lichrelových čísel, to znamená nejmenší číslo z každého proudu, které nevytváří palindrom. Základní číslo může být samo o sobě palindrom. První tři příklady jsou ve výše uvedeném seznamu tučně.

Související čísla jsou podmnožinou čísel Lichrel, která zahrnují všechna čísla proudu kromě základního, nebo jakékoli číslo, které se po jedné iteraci připojí k danému proudu. Termín zavedl Koji Yamashita v roce 1997.

Relé číslo 196

Vzhledem k tomu, že číslo 196 je nejmenším kandidátem na Lichrelova čísla, dostalo se mu největší pozornosti.

John Walker odstartoval štafetu 196 12. srpna 1987 na pracovní stanici Sun 3/260. Napsal program v jazyce C , který iteruje "flip and add" a po každém kroku kontroluje palindrom. Program běžel na pozadí s nízkou prioritou. Výsledky iterace uložila do souboru každé dvě hodiny a v době vypnutí systému, přičemž zaznamenala počet a počet dosažených iterací do té doby. Při každém zapnutí počítače se automaticky restartoval od posledního kontrolního bodu. Fungovalo to téměř tři roky a pak se zastavilo (jak bylo naprogramováno) 24. května 1990 se zprávou:

Zastávka na průjezdu 2 415 836 byla dosažena. Číslo obsahuje 1 000 000 číslic. Původní text  (anglicky)[ zobrazitskrýt] Bod zastavení dosažen na průsmyku 2,415,836.
Číslo obsahuje 1 000 000 číslic.

196 vzrostl na jeden milion číslic po 2 415 836 iteracích bez dosažení palindromu. Walker zveřejnil svá zjištění online spolu s posledním kontrolním bodem a vyzval ostatní, aby pokračovali v hledání na základě posledního dosaženého čísla.

V roce 1995 použil Tim Irwin tehdejší superpočítač a dosáhl hranice dvou milionů číslic za pouhé tři měsíce a opět nenašel palindrom. Jason Doucette se poté připojil k tomuto kvantitativnímu směru a v květnu 2000 dosáhl 12,5 milionu čísel. Wade VanLandingham pomocí programu Jasona Doucetteho dosáhl 13 milionů číslic, což bylo publikováno [9] v Yes Mag  , kanadském vědeckém časopise pro děti. Od června 2000 Wade VanLendingham nadále nesl vlajku pomocí programů napsaných různými nadšenci. 1. května 2006 dosáhl VanLendingham hranice 300 milionů číslic (v poměru jeden milion číslic každých 5-7 dní). Pomocí distribuovaného počítání provedl Romain Dolbeau ( fr. Romain Dolbeau ) v roce 2011 miliardu iterací a dostal číslo skládající se z 413 930 770 číslic [10] , v červenci 2012 jeho výpočty dosáhly čísla s 600 miliony číslic a v únoru 2015 čísla číslic přesáhl 1 miliardu [11] , ale palindrom nebyl nikdy objeven.

Ostatní kandidáti Lishrel, kteří byli podrobeni stejnému hledání, zahrnují 879, 1997, 7059 a další základní čísla: byli sledováni v milionech a desítkách milionů iterací, aniž by našli palindrom [12] [13] .

Poznámky

  1. ↑ Anton Stefanov (stefanov94). Odkládání palindromů na nový rok  (ruština)  // Habr: site. - 2021. - 5. ledna. Archivováno z originálu 7. ledna 2021.
  2. ↑ Dmitrij Maslov. Nalezen nejmenší zpožděný palindrom pro krok 289  (ruština)  // iLWN project: site. - 2021. - 14. října. Archivováno z originálu 6. listopadu 2021.
  3. ↑ Dmitrij Maslov. Byl stanoven nový světový rekord pro opožděné palindromy: 293 iterací!  (ruština)  // iLWN: web. - 2021. - 14. prosince. Archivováno z originálu 6. listopadu 2021.
  4. ↑ Archivovaná kopie . Získáno 29. května 2006. Archivováno z originálu 16. května 2006.
  5. ↑ Číselné obrácené součty vedoucí k palindromům (odkaz není k dispozici) . Datum přístupu: 4. ledna 2011. Archivováno z originálu 6. února 2010. 
  6. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 4. ledna 2011. Archivováno z originálu 18. března 2010. 
  7. ↑ Archivovaná kopie (odkaz není dostupný) . Datum přístupu: 4. ledna 2011. Archivováno z originálu 26. července 2010. 
  8. ↑ Archivovaná kopie . Získáno 15. října 2006. Archivováno z originálu 15. října 2006.
  9. ↑ Přichází nebo odchází?  (Angličtina)
  10. ↑ P196_mpi Implementace algoritmu Reverse-and-Add pro Palindrome Quest . Datum přístupu: 17. ledna 2015. Archivováno z originálu 19. dubna 2015.
  11. ↑ Stránka p196_mpi . Datum přístupu: 17. ledna 2015. Archivováno z originálu 11. února 2015.
  12. ↑ Lychrel Records . Archivováno z originálu 21. října 2006.
  13. ↑ Hledání palindromu 196 - projekt iLWN . Získáno 6. listopadu 2021. Archivováno z originálu dne 6. listopadu 2021.

Odkazy