Opgave 196

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. oktober 2019; checks kræver 44 redigeringer .

Problemet med tallet 196 er det betingede navn på et uløst matematisk problem : det vides ikke, om "vend og tilføj"-operationen anvendt på tallet 196 et vist antal gange vil føre til et palindrom .

Et Lychrel-tal er et naturligt tal , der ikke kan blive et palindrom ved hjælp af en iterativ "vend og tilføj"-proces i decimalnotation. Denne proces kaldes 196-algoritmen . Navnet Lychrel, opfundet af Wade VanLandingham , er et unøjagtigt anagram af hans kærestes navn , Cheryl . Der er ingen strengt beviste Lichrel-tal (for decimaltalsystemet; der er beviste Lichrel-tal for nogle andre talsystemer), men mange tal antages at være det, hvor det mindste er 196 .

Vend og fold

Operationen " Vend-og-tilføj " består i at tilføje det originale nummer med dets "omvendte" kopi, det vil sige et tal, hvis cifre er skrevet i omvendt rækkefølge. For eksempel, 56 + 65 = 121, 521 + 125 = 646.

Denne operation kan anvendes på ethvert naturligt tal. Hvis et palindrom opnås som et resultat af at anvende denne operation N gange på et bestemt antal , så kaldes et sådant tal "udskudt palindrom" , opløst i N iterationer. I modsætning til forsinkede palindromer resulterer denne operation for Lishrel-tal ikke i et palindrom, uanset hvor mange gange vi udfører det.

Nogle tal (især alle et-cifrede og næsten alle to-cifrede tal) bliver ret hurtigt til palindromer - efter blot at have udført nogle få operationer. Så omkring 80% af alle tal mindre end 10.000 løses til et palindrom i 4 eller færre iterationer. Omkring 91 % - i 7 eller færre iterationer. Og kun to tal - 89 og 98 - kræver usædvanligt meget: 24 operationer.

Her er nogle eksempler på forsinkede palindromer:

56 bliver til et palindrom efter én iteration: 56 + 65 = 121 .
57 bliver et palindrom efter to iterationer: 57 + 75 = 132, 132 + 231 = 363 .
59 bliver til et palindrom efter tre iterationer: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111 .
89 kræver usædvanligt lange 24 iterationer , før de når palindromet 8813200023188 (dette er det største antal operationer blandt tal op til 10000, som det videnskabelige samfund i øjeblikket med sikkerhed ved, at de løser til et palindrom).
10.911 når palindrom 4668731596684224866951378664 efter 55 iterationer .

Det mindste tal, der starter med 1 , der tilsyneladende ikke danner et palindrom, er det trecifrede tal 196 . Dette er det mindste kendte Lichrel potentielle decimaltal.

Mest forsinkede palindromer

Blandt det uendelige antal af forsinkede palindromer er de tal, der kræver det største antal iterationer for at blive et palindrom, særligt interessante.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ. Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Dette tal holdt verdensrekorden for de mest forsinkede palindromer i over 13 år.

I maj 2017 rapporterede TV-kanalen MIR24 , at skoledrengen Andrey Shchebetov fra Moskva havde opdaget det største kendte forsinkede palindrom, nummeret 1999291987030606810 . Der er dog intet interessant ved dette tal, da det opnås ved en simpel permutation af par af symmetriske cifre fra nummeret opdaget af Jason Doucette. Det største kendte 19-cifrede tal, der løses i 261 iterationer, er 1.999.999.936.042.548.910 , og det største kendte tal har 35 cifre .

Den 26. april 2019 satte Rob van Nobelen (hollandsk . Rob van Nobelen ) en ny verdensrekord for de mest forsinkede palindromer: det 23-cifrede nummer 12.000.700.000.025.339.936.491 , som bliver til et palindrom på 288 trin.

Den 5. januar 2021 offentliggjorde Anton Stefanov [1] de 23-cifrede numre 13,968,441,660,506,503,386,020 og 13,568,441,660,506,503,386,420 , som bliver til det samme nummer, som er fundet i en ny palindrome af Roben. Den 14. oktober 2021 rapporterede Dmitry Maslov [2] at han fandt et mindre 23-cifret tal, der løses i 289 iterationer: 10 036 069 400 174 999 499 950 .

Den 14. december 2021 satte Dmitry Maslov [3] en ny verdensrekord blandt de mest forsinkede palindromer: det 25-cifrede nummer 1000206827388999999095750 , som efter 293 iterationer bliver til et 132-cifret palindrom. Dette tal er den nuværende verdensrekord for de mest forsinkede palindromer.

Sekvensen OEIS A326414 indeholder 19353600 numre, der bliver til et palindrom efter 288 trin.

Sekvens A281506 indeholder en liste over 108864 forsinkede palindromer, der kræver 261 iterationer for at blive et palindrom. Det starter med 1186060307891929990 og slutter med 1999291987030606810 .

Formelforklaring

Lad os sige, at det er et naturligt tal. Vi definerer Lichrel-funktionen for grundtal (se relaterede definitioner) som følger: ${\mathcal {n))$ ${\textstyle b>1\ F_{b}:\mathbb {N} \rightarrow \mathbb {N} }$

${\displaystyle F_{b}(n)=n\ +\sum _{i=0}^{k-1}d_{i}b^{ki-1))$

hvor er antallet af cifre i grundtallet , og $k=\lgulv \log _{b}n\rgulv +1$ $b$

$d_{i}={\frac {n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i}}{b^{i}}}$

værdien af hvert ciffer i tallet. Et tal er et Lichrel-tal, hvis der ikke er noget naturligt tal , således at , hvor er iterationer $jeg$ $F_{b}^{i+1}(n)=2F_{b}^{i}(n)$ $F^i$ $jeg$ $F$

Nyt problem

I andre talsystemer kan nogle tal bevises, at de aldrig danner et palindrom efter successive iterationer [4] [5] , men der er ikke fundet et sådant bevis for 196 og andre decimaltal.

Der er en formodning om, at 196 og andre tal, der endnu ikke er blevet et palindrom, er Lishrel-tal, men der er ingen strenge beviser for noget tal, at de er. Sådanne numre omtales uformelt som "kandidater til Lichrel-numrene". De første par kandidater til Lychrel-numrene er sekvensen A023108 i OEIS :

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

De med fed skrift betragtes som basislychrel-numre (se nedenfor ). Jason Doucettes, Jan Peters og Benjamin Despres' computerprogrammer fandt andre Lishrel-kandidater. Desuden identificerede Benjamin Despres alle base Lichrel-numre med mindre end 17 cifre [6] . Wade VanLandinghams websted indeholder lister over Lychrel-basisnumre for hver tallængde. [7]

Brute force-metoden , oprindeligt udviklet af John Walker, er blevet forbedret for at drage fordel af iterationsadfærden. For eksempel er der et program oprettet af Won Suite, der kun gemmer de første og sidste par cifre i hver iteration, så du kan teste digitale mønstre over millioner af iterationer uden at skulle gemme hver iteration i en fil [8] . Men indtil videre er der ikke opfundet nogen algoritme , der ville omgå den iterative proces.

Relaterede definitioner

Udtrykket tråd eller tråd ( engelsk tråd ) blev opfundet af Jason Doucette, der betegner rækkefølgen af tal opnået som et resultat af iterationer af det oprindelige nummer. Basistallet ( eng. frø ) og dets relaterede relaterede ( eng. kin ) tal konvergerer i én strøm. Strømmen inkluderer ikke det oprindelige grundtal eller dets relative , men kun de tal, der er fælles for begge, efter at de er konvergeret.

Basistallene er en undersekvens af Lichrel-tal, det vil sige det mindste tal fra hver strøm, der ikke producerer et palindrom. Basistallet kan i sig selv være et palindrom. De første tre eksempler er med fed skrift på listen ovenfor.

Relaterede tal er en delmængde af Lichrel-tal, der inkluderer alle numrene i strømmen undtagen grundtallet, eller et hvilket som helst tal, der vil slutte sig til den givne strøm efter én iteration. Udtrykket blev introduceret af Koji Yamashita i 1997.

Relæ nummer 196

Da tallet 196 er den mindste kandidat til Lichrel-tallene, har det fået mest opmærksomhed.

John Walker startede 196-stafetten den 12. august 1987 ved Sun arbejdsstation 3/260. Han skrev et C -program , der gentager "vend og tilføj" og kontrollerer for et palindrom efter hvert trin. Programmet kørte i baggrunden med lav prioritet. Hun dumpede iterationsresultaterne i en fil hver anden time og på tidspunktet for systemets nedlukning, og registrerede antallet og iterationsnummeret, som hun nåede på det tidspunkt. Den genstartede sig selv automatisk fra det sidste kontrolpunkt, hver gang computeren blev tændt. Det virkede i næsten tre år og stoppede derefter (som programmeret) den 24. maj 1990 med beskeden:

Stoppunktet ved pas 2 415 836 er nået. Nummeret indeholder 1.000.000 cifre. Originaltekst (engelsk)[ Visskjule] Stoppunkt nået på pas 2.415.836.
Nummeret indeholder 1.000.000 cifre.

196 steg til en million cifre efter 2.415.836 iterationer uden at nå et palindrom. Walker lagde sine resultater online sammen med det sidste kontrolpunkt, og inviterede andre til at genoptage deres søgning baseret på det sidste antal nåede.

I 1995 brugte Tim Irwin disse års supercomputer og nåede to millioner cifre på kun tre måneder, igen uden at finde et palindrom. Jason Doucette sluttede sig derefter til denne kvantitative retning og nåede 12,5 millioner tal i maj 2000. Wade VanLandingham, ved hjælp af Jason Doucettes program, nåede 13 millioner cifre, som blev offentliggjort [9] i Yes Mag , et canadisk videnskabsmagasin for børn. Siden juni 2000 har Wade VanLendingham fortsat med at bære flaget ved hjælp af programmer skrevet af forskellige entusiaster. Den 1. maj 2006 nåede VanLendingham 300 millioner cifre (med en hastighed på en million cifre hver 5.-7. dag). Ved hjælp af distribueret databehandling lavede Romain Dolbeau ( fr. Romain Dolbeau ) i 2011 en milliard iterationer og fik et tal bestående af 413.930.770 cifre [10] , i juli 2012 nåede hans beregninger et tal med 600 millioner cifre, og i februar 2015 talcifrene oversteg 1 milliard [11] , men palindromet blev aldrig opdaget.

Andre Lishrel-kandidater, der har været udsat for den samme søgning, omfatter 879, 1997, 7059 og andre basistal: de er blevet sporet over millioner og titusinder af iterationer uden at finde et palindrom [12] [13] .

Noter

↑ Anton Stefanov (stefanov94). Udsættelse af palindromer til det nye år (russisk) // Habr: site. - 2021. - 5. januar. Arkiveret fra originalen den 7. januar 2021.
↑ Dmitry Maslov. Fandt det mindste forsinkede palindrom til trin 289 (russisk) // iLWN-projekt: site. - 2021. - 14. oktober. Arkiveret fra originalen den 6. november 2021.
↑ Dmitry Maslov. En ny verdensrekord for forsinkede palindromer er blevet sat: 293 iterationer! (russisk) // iLWN: websted. - 2021. - 14. december. Arkiveret fra originalen den 6. november 2021.
↑ Arkiveret kopi . Hentet 29. maj 2006. Arkiveret fra originalen 16. maj 2006. (ubestemt)
↑ Ciffertilbageførselssummer, der fører til palindromer (link ikke tilgængeligt) . Dato for adgang: 4. januar 2011. Arkiveret fra originalen 6. februar 2010. (ubestemt)
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 4. januar 2011. Arkiveret fra originalen 18. marts 2010. (ubestemt)
↑ Arkiveret kopi (link ikke tilgængeligt) . Dato for adgang: 4. januar 2011. Arkiveret fra originalen den 26. juli 2010. (ubestemt)
↑ Arkiveret kopi . Hentet 15. oktober 2006. Arkiveret fra originalen 15. oktober 2006. (ubestemt)
↑ Kommer eller går? (Engelsk)
↑ p196_mpi-implementeringen af Reverse-And-Add-algoritmen for Palindrome Quest . Dato for adgang: 17. januar 2015. Arkiveret fra originalen 19. april 2015. (ubestemt)
↑ Siden p196_mpi . Dato for adgang: 17. januar 2015. Arkiveret fra originalen 11. februar 2015. (ubestemt)
↑ Lychrel Records . Arkiveret fra originalen den 21. oktober 2006. (ubestemt)
↑ At finde palindrome 196 - iLWN-projektet . Hentet 6. november 2021. Arkiveret fra originalen 6. november 2021. (ubestemt)