Problem 196

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 oktober 2019; kontroller kräver 44 redigeringar .

Problemet med siffran 196  är det villkorliga namnet på ett olöst matematiskt problem : det är inte känt om operationen "vänd och lägg till" som tillämpas på siffran 196 ett visst antal gånger kommer att leda till en palindrom .

Ett Lychrel-tal är ett  naturligt tal som inte kan bli ett palindrom med en iterativ "vänd och lägg"-process i decimalnotation. Denna process kallas 196-algoritmen . Namnet Lychrel, myntat av Wade VanLandingham , är ett felaktigt anagram av hans flickväns namn , Cheryl . Det finns inga noggrant bevisade Lichrel-tal (för decimaltalssystemet; det finns bevisade Lichrel-tal för vissa andra talsystem), men många tal antas vara det, där det minsta är 196 .   

Vänd och vik

Operationen " Reverse-and-add "  består i att lägga till originalnumret med dess "omvända" kopia, det vill säga ett nummer vars siffror skrivs i omvänd ordning. Till exempel, 56 + 65 = 121, 521 + 125 = 646.

Denna operation kan tillämpas på vilket naturligt tal som helst. Om ett palindrom erhålls som ett resultat av att tillämpa denna operation N gånger på ett visst antal, kallas ett sådant tal "uppskjuten palindrom" , upplöst i N iterationer. Till skillnad från fördröjda palindromer, för Lishrel-tal resulterar denna operation inte i ett palindrom, oavsett hur många gånger vi utför det.

Vissa siffror (särskilt alla ensiffriga och nästan alla tvåsiffriga siffror) blir palindromer ganska snabbt - efter bara några få operationer. Så cirka 80% av alla siffror mindre än 10 000 löser sig till en palindrom i 4 eller färre iterationer. Cirka 91 % - i 7 eller färre iterationer. Och bara två nummer - 89 och 98 - kräver ovanligt mycket: 24 operationer.

Här är några exempel på fördröjda palindromer:

Det minsta talet, som börjar med 1 , som tydligen inte bildar ett palindrom är det tresiffriga talet 196 . Detta är det minsta kända Lichrel potentiella decimaltalet.

Mest fördröjda palindromer

Bland det oändliga antalet fördröjda palindromer är de siffror som kräver flest iterationer för att bli en palindrom särskilt intressanta.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ.  Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Detta antal hade världsrekordet för de mest försenade palindromerna i över 13 år.

I maj 2017 rapporterade TV-kanalen MIR24 att skolpojken Andrey Shchebetov i Moskva hade upptäckt den största kända försenade palindromen, numret 1999291987030606810 . Det finns dock inget intressant med detta nummer, eftersom det erhålls genom en enkel permutation av par av symmetriska siffror från numret som upptäcktes av Jason Doucette. Det största kända 19-siffriga numret som löses i 261 iterationer är 1 999 999 936 042 548 910 , och det största kända numret har 35 siffror .

Den 26 april 2019 satte Rob van Nobelen (holländska . Rob van Nobelen ) ett nytt världsrekord för de mest försenade palindromerna: det 23-siffriga numret 12 000 700 000 025 339 936 491 , som förvandlas till en palindrom på 288 steg.

Den 5 januari 2021 publicerade Anton Stefanov [1] de 23-siffriga siffrorna 13,968,441,660,506,503,386,020 och 13,568,441,660,506,503,386,420 , som förvandlas till samma nummer 28, som funnits i samma nummer som Robbens rekord. Den 14 oktober 2021 rapporterade Dmitry Maslov [2] att han hittade ett mindre 23-siffrigt tal som löser sig i 289 iterationer: 10 036 069 400 174 999 499 950 .

Den 14 december 2021 satte Dmitry Maslov [3] ett nytt världsrekord bland de mest försenade palindromerna: det 25-siffriga numret 1000206827388999999095750 , som efter 293 iterationer blir en 132-siffrig palindrom. Detta nummer är det nuvarande världsrekordet för de mest försenade palindromerna.

Sekvensen OEIS A326414 innehåller 19353600 nummer som förvandlas till en palindrom efter 288 steg.

Sekvens A281506 innehåller en lista med 108864 fördröjda palindromer, som kräver 261 iterationer för att bli en palindrom. Det börjar med 1186060307891929990 och slutar med 1999291987030606810 .

Formelförklaring

Låt oss säga att det är ett naturligt tal. Vi definierar Lichrel-funktionen för bastal (se relaterade definitioner) enligt följande:

var är antalet siffror i basnumret , och

värdet av varje siffra i numret. Ett tal är ett Lichrel-tal om det inte finns något naturligt tal så att , där är iterationer

Nytt problem

I andra talsystem kan vissa siffror bevisas att de aldrig bildar ett palindrom efter successiva iterationer [4] [5] , men inga sådana bevis har hittats för 196 och andra decimaltal.

Det finns en gissning om att 196 och andra siffror som ännu inte har blivit ett palindrom är Lishrel-tal, men det finns inga rigorösa bevis för något tal att de är. Sådana nummer kallas informellt "kandidater till Lichrel-numren". De första få kandidaterna för Lychrel-numren är 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 i fet stil betraktas som baslychrelnummer (se nedan ). Datorprogrammen för Jason Doucette, Jan Peters och Benjamin Despres hittade andra Lishrel-kandidater. Dessutom identifierade Benjamin Despres alla Lichrel-basnummer med mindre än 17 siffror [6] . Wade VanLandinghams webbplats innehåller listor över Lychrel-basnummer för varje nummerlängd. [7]

Den brute force-metoden , som ursprungligen utvecklades av John Walker, har förbättrats för att dra fördel av iterationsbeteendet. Till exempel finns det ett program skapat av Won Suite som endast sparar de första och sista siffrorna i varje iteration, vilket gör att du kan testa digitala mönster över miljontals iterationer utan att behöva spara varje iteration till en fil [8] . Men hittills har ingen algoritm uppfunnits som skulle kringgå den iterativa processen.

Relaterade definitioner

Termen tråd eller tråd ( engelsk  tråd ) uppfanns av Jason Doucette, vilket betecknar sekvensen av nummer som erhålls som ett resultat av iterationer av det ursprungliga numret. Bastalet ( eng.  seed ) och dess relaterade relaterade ( eng.  kin ) tal konvergerar i en ström. Strömmen inkluderar inte det ursprungliga basnumret eller dess relativa , utan bara de tal som är gemensamma för båda, efter att de konvergerar.

Bastalen är en undersekvens av Lichrel-tal, det vill säga det minsta antalet från varje ström som inte producerar en palindrom. Bastalet kan i sig vara ett palindrom. De tre första exemplen är i fetstil i listan ovan.

Relaterade siffror är en delmängd av Lichrel-tal som inkluderar alla siffror i strömmen utom basen, eller vilket nummer som helst som kommer att gå med i den givna strömmen efter en iteration. Termen introducerades av Koji Yamashita 1997.

Relä nummer 196

Eftersom siffran 196 är den minsta kandidaten för Lichrel-talen har den fått mest uppmärksamhet.

John Walker startade 196 stafetten den 12 augusti 1987 vid Sun arbetsstation 3/260. Han skrev ett C -program som itererar "vänd och lägg till" och kontrollerar efter ett palindrom efter varje steg. Programmet kördes i bakgrunden med låg prioritet. Hon dumpade iterationsresultaten i en fil varannan timme och vid tidpunkten för systemets avstängning, och registrerade antalet och iterationsnumret som nåddes vid den tiden. Den startade om sig själv automatiskt från den senaste kontrollpunkten varje gång datorn slogs på. Det fungerade i nästan tre år och slutade sedan (som programmerat) den 24 maj 1990 med meddelandet:

Stoppplatsen vid pass 2 415 836 har nåtts. Numret innehåller 1 000 000 siffror. Originaltext  (engelska)[ visaDölj] Stopppunkt nådd på pass 2 415 836.
Numret innehåller 1 000 000 siffror.

196 ökade till en miljon siffror efter 2 415 836 iterationer utan att nå en palindrom. Walker publicerade sina fynd på nätet tillsammans med den sista checkpointen, och uppmanade andra att återuppta sin sökning baserat på det senast nådda antalet.

År 1995 använde Tim Irwin superdatorn från dessa år och nådde två miljoner siffror på bara tre månader, utan att återigen hitta ett palindrom. Jason Doucette anslöt sig sedan till denna kvantitativa riktning och nådde 12,5 miljoner siffror i maj 2000. Wade VanLandingham, med hjälp av Jason Doucettes program, nådde 13 miljoner siffror, vilket publicerades [9] i Yes Mag  , en kanadensisk vetenskapstidskrift för barn. Sedan juni 2000 har Wade VanLendingham fortsatt att bära flaggan, med hjälp av program skrivna av olika entusiaster. Den 1 maj 2006 nådde VanLendingham 300 miljoner siffror (med en takt på en miljon siffror var 5-7 dag). Med hjälp av distribuerad beräkning gjorde Romain Dolbeau ( fr. Romain Dolbeau ) 2011 en miljard iterationer och fick ett tal bestående av 413 930 770 siffror [10] , i juli 2012 nådde hans beräkningar ett tal med 600 miljoner siffror och i februari 2015 siffror översteg 1 miljard [11] , men palindromen upptäcktes aldrig.

Andra Lishrel-kandidater som har utsatts för samma sökning inkluderar 879, 1997, 7059 och andra bastal: de har spårats över miljoner och tiotals miljoner iterationer utan att hitta ett palindrom [12] [13] .

Anteckningar

  1. ↑ Anton Stefanov (stefanov94). Att skjuta upp palindromer för det nya året  (ryska)  // Habr: webbplats. - 2021. - 5 januari. Arkiverad från originalet den 7 januari 2021.
  2. ↑ Dmitrij Maslov. Hittade den minsta fördröjda palindromen för steg 289  (ryska)  // iLWN-projekt: webbplats. - 2021. - 14 oktober. Arkiverad från originalet den 6 november 2021.
  3. ↑ Dmitrij Maslov. Ett nytt världsrekord för försenade palindromer har satts: 293 iterationer!  (ryska)  // iLWN: webbplats. - 2021. - 14 december. Arkiverad från originalet den 6 november 2021.
  4. ↑ Arkiverad kopia . Hämtad 29 maj 2006. Arkiverad från originalet 16 maj 2006.
  5. ↑ Summor för omkastning av siffror som leder till palindromer (länk ej tillgänglig) . Tillträdesdatum: 4 januari 2011. Arkiverad från originalet den 6 februari 2010. 
  6. ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 4 januari 2011. Arkiverad från originalet 18 mars 2010. 
  7. ↑ Arkiverad kopia (länk ej tillgänglig) . Datum för åtkomst: 4 januari 2011. Arkiverad från originalet den 26 juli 2010. 
  8. ↑ Arkiverad kopia . Hämtad 15 oktober 2006. Arkiverad från originalet 15 oktober 2006.
  9. ↑ Kommer eller går?  (Engelsk)
  10. ↑ P196_mpi-implementeringen av Reverse-And-Add-algoritmen för Palindrome Quest . Tillträdesdatum: 17 januari 2015. Arkiverad från originalet 19 april 2015.
  11. ↑ Sidan p196_mpi . Tillträdesdatum: 17 januari 2015. Arkiverad från originalet 11 februari 2015.
  12. ↑ Lychrel Records . Arkiverad från originalet den 21 oktober 2006.
  13. ^ Hitta palindrom 196 - iLWN-projekt . Hämtad 6 november 2021. Arkiverad från originalet 6 november 2021.

Länkar