Problema 196

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 octombrie 2019; verificările necesită 44 de modificări .

Problema numărului 196  este denumirea condiționată a unei probleme matematice nerezolvate : nu se știe dacă operația „întoarce și adaugă” aplicată numărului 196 de un anumit număr de ori va duce la un palindrom .

Un număr Lychrel este un  număr natural care nu poate deveni un palindrom folosind un proces iterativ de „întorsătură și adăugare” în notație zecimală. Acest proces se numește algoritmul 196 . Numele Lychrel, inventat de Wade VanLandingham , este o anagramă inexactă a numelui iubitei sale , Cheryl . Nu există numere Lichrel dovedite riguros (pentru sistemul numeric zecimal; există numere Lichrel dovedite pentru alte sisteme de numere), dar se presupune că multe numere sunt astfel, cel mai mic fiind 196 .   

Întoarce și pliază

Operația „ Reverse-and-add ”  constă în adăugarea numărului original cu copia sa „inversată”, adică un număr ale cărui cifre sunt scrise în ordine inversă. De exemplu, 56 + 65 = 121, 521 + 125 = 646.

Această operație poate fi aplicată oricărui număr natural. Dacă în urma aplicării acestei operații de N ori la un anumit număr se obține un palindrom , atunci un astfel de număr se numește „palindrom amânat” , rezolvat în N iterații. Spre deosebire de palindromurile întârziate, pentru numerele Lishrel această operație nu are ca rezultat un palindrom, indiferent de câte ori îl executăm.

Unele numere (în special, toate numerele de o cifră și aproape toate numerele de două cifre) devin palindromuri destul de repede - după aplicarea doar a câtorva operații. Deci, aproximativ 80% din toate numerele mai mici de 10.000 se rezolvă la un palindrom în 4 sau mai puține iterații. Aproximativ 91% - în 7 sau mai puține iterații. Și doar două numere - 89 și 98 - necesită o cantitate neobișnuit de mare: 24 de operații.

Iată câteva exemple de palindromuri întârziate:

Cel mai mic număr, începând cu 1 , care aparent nu formează un palindrom este numărul de trei cifre 196 . Acesta este cel mai mic număr zecimal potențial Lichrel cunoscut.

Cele mai multe palindromuri întârziate

Dintre numărul infinit de palindromuri întârziate, sunt deosebit de interesante acele numere care necesită cel mai mare număr de iterații pentru a deveni palindrom.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ.  Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Acest număr a deținut recordul mondial pentru cele mai întârziate palindromuri de peste 13 ani.

În mai 2017, postul de televiziune MIR24 a raportat că școlarul din Moscova Andrey Șcebetov a descoperit cel mai mare palindrom întârziat cunoscut, numărul 1999291987030606810 . Cu toate acestea, nu este nimic interesant la acest număr, deoarece este obținut printr-o simplă permutare a perechilor de cifre simetrice din numărul descoperit de Jason Doucette. Cel mai mare număr cunoscut de 19 cifre care se rezolvă în 261 de iterații este 1.999.999.936.042.548.910 , iar cel mai mare număr cunoscut are 35 de cifre .

Pe 26 aprilie 2019, Rob van Nobelen (olandeză . Rob van Nobelen ) a stabilit un nou record mondial pentru cele mai întârziate palindroame: numărul de 23 de cifre 12.000.700.000.025.339.936.491 , care se transformă într-un palindrom în 288 de pași.

Pe 5 ianuarie 2021, Anton Stefanov a publicat [1] numerele din 23 de cifre 13.968.441.660.506.503.386.020 și 13.568.441.660.506.503.386.420 , care se transformă în același număr de 2 pal8, găsit de Robindrome, într-un nou record găsit de Roben Step. Pe 14 octombrie 2021, Dmitri Maslov a raportat [2] că a găsit un număr mai mic de 23 de cifre care se rezolvă în 289 de iterații: 10 036 069 400 174 999 499 950 .

Pe 14 decembrie 2021, Dmitri Maslov a stabilit [3] un nou record mondial printre cele mai întârziate palindroame: numărul de 25 de cifre 100020682738999999095750 , care după 293 de iterații devine un palindrom de 132 de cifre. Acest număr este recordul mondial actual pentru cele mai întârziate palindroame.

Secvența OEIS A326414 conține 19353600 de numere care se transformă în palindrom după 288 de pași.

Secvența A281506 conține o listă de 108864 palindromuri întârziate, necesitând 261 de iterații pentru a deveni un palindrom. Începe cu 1186060307891929990 și se termină cu 1999291987030606810 .

Explicația formulei

Să spunem că este un număr natural. Definim funcția Lichrel pentru numerele de bază (vezi definițiile aferente) după cum urmează:

unde este numărul de cifre din numărul de bază și

valoarea fiecărei cifre a numărului. Un număr este un număr Lichrel dacă nu există un număr natural astfel încât , unde este iterații

Problemă nouă

În alte sisteme numerice, se poate dovedi că unele numere nu formează niciodată un palindrom după iterații succesive [4] [5] , dar nu au fost găsite astfel de dovezi pentru 196 și alte numere zecimale.

Există o presupunere că 196 și alte numere care nu au devenit încă un palindrom sunt numere Lishrel, dar nu există dovezi riguroase pentru niciun număr că sunt. Astfel de numere sunt denumite în mod informal „candidați pentru numerele Lichrel”. Primii câțiva candidați pentru numerele Lychrel sunt secvența A023108 din OEIS :

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

Cele îngroșate sunt considerate numere Lychrel de bază (vezi mai jos ). Programele de calculator ale lui Jason Doucette, Jan Peters și Benjamin Despres au găsit alți candidați Lishrel. Mai mult, Benjamin Despres a identificat toate numerele Lichrel de bază cu mai puțin de 17 cifre [6] . Site-ul lui Wade VanLandingham conține liste cu numere de bază Lychrel pentru fiecare lungime de număr. [7]

Metoda forței brute , dezvoltată inițial de John Walker, a fost îmbunătățită pentru a profita de comportamentul de iterație. De exemplu, există un program creat de Won Suite care salvează doar primele și ultimele cifre ale fiecărei iterații, permițându-vă să testați modele digitale pe milioane de iterații fără a fi nevoie să salvați fiecare iterație într-un fișier [8] . Dar până acum nu a fost inventat niciun algoritm care să ocolească procesul iterativ.

Definiții înrudite

Termenul fir sau fir ( fir englezesc  ) a fost inventat de Jason Doucette, desemnând succesiunea de numere obținute ca urmare a iterațiilor numărului original. Numărul de bază ( eng. seed ) și numerele aferente acestuia ( eng . kin ) converg într-un singur flux. Fluxul nu include numărul de bază inițial sau relativul acestuia , ci doar numerele care sunt comune ambelor, după ce acestea converg.   

Numerele de bază sunt o subsecvență a numerelor Lichrel, adică cel mai mic număr din fiecare flux care nu produce un palindrom. Numărul de bază poate fi el însuși un palindrom. Primele trei exemple sunt cu caractere aldine în lista de mai sus.

Numerele înrudite sunt un subset de numere Lichrel care includ toate numerele fluxului, cu excepția celui de bază, sau orice număr care se va alătura fluxului dat după o iterație. Termenul a fost introdus de Koji Yamashita în 1997.

Stafeta numarul 196

Deoarece numărul 196 este cel mai mic candidat pentru numerele Lichrel, a primit cea mai mare atenție.

John Walker a început ștafeta 196 pe 12 august 1987 la stația de lucru Sun 3/260. El a scris un program C care repetă „întoarce și adaugă” și verifică un palindrom după fiecare pas. Programul rula în fundal cu o prioritate scăzută. Ea a aruncat rezultatele iterației într-un fișier la fiecare două ore și, în momentul închiderii sistemului, înregistrând numărul și numărul iterației atinse până în acel moment. S-a repornit automat de la ultimul punct de control de fiecare dată când computerul a fost pornit. A funcționat aproape trei ani și apoi s-a oprit (așa cum era programat) pe 24 mai 1990 cu mesajul:

Punctul de oprire de la trecerea 2 415 836 a fost atins. Numărul conține 1.000.000 de cifre. Text original  (engleză)[ arataascunde] Punct de oprire atins pe trecerea 2.415.836.
Numărul conține 1.000.000 de cifre.

196 a crescut la un milion de cifre după 2.415.836 de iterații fără a ajunge la un palindrom. Walker și-a postat descoperirile online împreună cu ultimul punct de control, invitându-i pe alții să-și reia căutarea pe baza ultimului număr atins.

În 1995, Tim Irwin a folosit supercalculatorul acelor ani, atingând marca a două milioane de cifre în doar trei luni, din nou negăsind un palindrom. Jason Doucette s-a alăturat apoi acestei direcții cantitative și a atins 12,5 milioane de cifre în mai 2000. Wade VanLandingham, folosind programul lui Jason Doucette, a atins 13 milioane de cifre, care a fost publicat [9] în Yes Mag  , o revistă canadiană de știință pentru copii. Din iunie 2000, Wade VanLendingham a continuat să poarte steagul, folosind programe scrise de diverși entuziaști. Până la 1 mai 2006, VanLendingham a atins pragul de 300 de milioane de cifre (cu o rată de un milion de cifre la fiecare 5-7 zile). Folosind calculul distribuit , în 2011 Romain Dolbeau ( fr. Romain Dolbeau ) a făcut un miliard de iterații și a obținut un număr format din 413.930.770 de cifre [10] , în iulie 2012 calculele sale au ajuns la un număr de 600 de milioane de cifre, iar în februarie numărul de 201 de cifre . a depășit 1 miliard [11] , dar palindromul nu a fost niciodată descoperit.

Alți candidați Lishrel care au fost supuși aceleiași căutări includ 879, 1997, 7059 și alte numere de bază: au fost urmăriți pe milioane și zeci de milioane de iterații fără a găsi un palindrom [12] [13] .

Note

  1. ↑ Anton Stefanov (stefanov94). Amânarea palindromilor pentru noul an  (rusă)  // Habr: site. - 2021. - 5 ianuarie. Arhivat din original pe 7 ianuarie 2021.
  2. ↑ Dmitri Maslov. S-a găsit cel mai mic palindrom întârziat pentru pasul 289  (rusă)  // proiect iLWN: site. - 2021. - 14 octombrie. Arhivat din original pe 6 noiembrie 2021.
  3. ↑ Dmitri Maslov. A fost stabilit un nou record mondial pentru palindromurile întârziate: 293 de iterații!  (rusă)  // iLWN: site. - 2021. - 14 decembrie. Arhivat din original pe 6 noiembrie 2021.
  4. ↑ Copie arhivată . Consultat la 29 mai 2006. Arhivat din original pe 16 mai 2006.
  5. ↑ Sumele inversate de cifre care conduc la palindrom (link nu este disponibil) . Data accesului: 4 ianuarie 2011. Arhivat din original pe 6 februarie 2010. 
  6. ↑ Copie arhivată (link nu este disponibil) . Consultat la 4 ianuarie 2011. Arhivat din original pe 18 martie 2010. 
  7. ↑ Copie arhivată (link nu este disponibil) . Data accesului: 4 ianuarie 2011. Arhivat din original pe 26 iulie 2010. 
  8. ↑ Copie arhivată . Consultat la 15 octombrie 2006. Arhivat din original pe 15 octombrie 2006.
  9. ↑ Vin sau plec?  (Engleză)
  10. ↑ Implementarea p196_mpi a algoritmului Reverse-And-Add pentru Palindrom Quest . Data accesului: 17 ianuarie 2015. Arhivat din original pe 19 aprilie 2015.
  11. ↑ Pagina p196_mpi . Data accesului: 17 ianuarie 2015. Arhivat din original pe 11 februarie 2015.
  12. ↑ Lychrel Records . Arhivat din original pe 21 octombrie 2006.
  13. ↑ Găsirea palindromului 196 - proiect iLWN . Preluat la 6 noiembrie 2021. Arhivat din original la 6 noiembrie 2021.

Link -uri