Ongelma 196

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. lokakuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 44 muokkausta .

Numeron 196 ongelma on ratkaisemattoman matemaattisen ongelman ehdollinen nimi : ei tiedetä, johtaako numeroon 196 tietyn määrän kertoja sovellettu "käännä ja lisää" -operaatio palindromiin .

Lychrel -luku on luonnollinen luku , josta ei voi tulla palindromia käyttämällä iteratiivista "käännä ja lisää" -prosessia desimaalimuodossa. Tätä prosessia kutsutaan 196-algoritmiksi . Wade VanLandinghamin keksimä nimi Lychrel on epätarkka anagrammi hänen tyttöystävänsä nimestä Cheryl . Ei ole tiukasti todistettuja Lichrel-lukuja (desimaalilukujärjestelmälle; on olemassa todistettuja Lichrel-lukuja joillekin muille lukujärjestelmille), mutta monien lukujen oletetaan olevan niin, pienin on 196 .

Käännä ja taita

" Käännä ja lisää " -toiminto koostuu alkuperäisen numeron lisäämisestä sen " käänteiseen" kopioon, eli numeroon, jonka numerot on kirjoitettu käänteisessä järjestyksessä. Esimerkiksi 56 + 65 = 121, 521 + 125 = 646.

Tätä operaatiota voidaan soveltaa mihin tahansa luonnolliseen lukuun. Jos tämän operaation N kertaa soveltamisen tuloksena tiettyyn lukuon saadaan palindromi , niin tällaista lukua kutsutaan "lykätyksi palindromiksi" , joka ratkaistaan N iteraatiolla. Toisin kuin viivästetyt palindromit, Lishrel-luvuille tämä operaatio ei johda palindromiin, vaikka kuinka monta kertaa sen suoritamme.

Jotkut luvut (erityisesti kaikki yksinumeroiset ja lähes kaikki kaksinumeroiset luvut) muuttuvat palindromeiksi melko nopeasti - vain muutaman toiminnon jälkeen. Joten noin 80 % kaikista alle 10 000:n luvuista ratkeaa palindromiksi neljässä tai pienemmässä iteraatiossa. Noin 91 % - 7 tai vähemmän iteraatiossa. Ja vain kaksi numeroa - 89 ja 98 - vaativat epätavallisen suuren määrän: 24 operaatiota.

Tässä on esimerkkejä viivästyneistä palindromeista:

56:sta tulee palindromi yhden iteroinnin jälkeen: 56 + 65 = 121 .
57:stä tulee palindromi kahden iteroinnin jälkeen: 57 + 75 = 132, 132 + 231 = 363 .
59:stä tulee palindromi kolmen iteroinnin jälkeen: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111 .
89 vaatii epätavallisen pitkiä 24 iteraatiota ennen kuin se saavuttaa palindromin 8813200023188 (tämä on suurin operaatioiden määrä 10 000 asti, jonka tiedeyhteisö tietää tällä hetkellä varmasti niiden ratkaisevan palindromiksi).
10 911 saavuttaa palindromin 4668731596684224866951378664 55 iteroinnin jälkeen .

Pienin numerolla 1 alkava luku, joka ei ilmeisesti muodosta palindromia, on kolminumeroinen luku 196 . Tämä on pienin tunnettu Lichrel-potentiaalinen desimaaliluku.

Useimmat viivästyneet palindromit

Loputtomien viivästyneiden palindromien joukossa ne luvut, jotka vaativat eniten iteraatioita tullakseen palindromiksi, ovat erityisen mielenkiintoisia.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ. Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Tämä numero piti eniten viivästyneiden palindromien maailmanennätystä yli 13 vuoden ajan.

Toukokuussa 2017 TV-kanava MIR24 kertoi, että Moskovan koulupoika Andrey Shchebetov oli löytänyt suurimman tunnetun viivästyneen palindromin, numeron 1999291987030606810 . Tässä numerossa ei kuitenkaan ole mitään mielenkiintoista, koska se saadaan yksinkertaisella symmetristen numeroparien permutaatiolla Jason Doucetten löytämästä numerosta. Suurin tunnettu 19-numeroinen luku, joka selviää 261 iteraatiossa, on 1 999 999 936 042 548 910 ja suurimmassa tunnetussa luvussa on 35 numeroa .

Rob van Nobelen (hollantilainen . Rob van Nobelen ) teki 26. huhtikuuta 2019 uuden maailmanennätyksen eniten viivästyneissä palindromeissa: 23-numeroisen luvun 12 000 700 000 025 339 936 491 , joka muuttuu palindromiksi 288 askelmassa.

5. tammikuuta 2021 Anton Stefanov julkaisi [1] 23-numeroiset luvut 13 968 441 660 506 503 386 020 ja 13 568 441 660 506 503 386 420 , jotka muuttuvat uudeksi asetukseksi Robbel9 ennätys . 14. lokakuuta 2021 Dmitri Maslov raportoi [2] löytäneensä pienemmän 23-numeroisen luvun, joka selviää 289 iteraatiossa: 10 036 069 400 174 999 499 950 .

14. joulukuuta 2021 Dmitri Maslov asetti [3] uuden maailmanennätyksen viivästyneimpien palindromien joukossa: 25-numeroisen numeron 1000206827388999999095750 , josta tulee 293 iteroinnin jälkeen 132-numeroinen palindromi. Tämä luku on nykyinen maailmanennätys eniten viivästyneissä palindromeissa.

Sarja OEIS A326414 sisältää 19353600 numeroa, jotka muuttuvat palindromiksi 288 askeleen jälkeen.

Sekvenssi A281506 sisältää luettelon 108 864 viivästetystä palindromista, jotka vaativat 261 iteraatiota tullakseen palindromiksi. Se alkaa numerolla 1186060307891929990 ja päättyy numeroon 1999291987030606810 .

Kaavan selitys

Oletetaan, että se on luonnollinen luku. Määrittelemme Lichrel-funktion perusnumeroille ( katso liittyvät määritelmät) seuraavasti: ${\mathcal {n))$ ${\textstyle b>1\ F_{b}:\mathbb {N} \rightarrow \mathbb {N} }$

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

missä on perusluvun numeroiden määrä , ja $k=\lfloor \log _{b}n\rfloor +1$ $b$

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

luvun jokaisen numeron arvo. Luku on Lichrel-luku , jos ei ole luonnollista lukua , jossa on iteraatioita $i$ $F_{b}^{i+1}(n)=2F_{b}^{i}(n)$ $F^i$ $i$ $F$

Uusi ongelma

Muissa lukujärjestelmissä jotkin luvut voidaan todistaa, etteivät ne koskaan muodosta palindromia peräkkäisten iteraatioiden jälkeen [4] [5] , mutta 196:sta ja muista desimaaliluvuista ei ole löydetty tällaista näyttöä.

Oletuksena on , että 196 ja muut luvut, joista ei ole vielä tullut palindromia, ovat Lishrel -lukuja, mutta niiden olemassaolosta ei ole olemassa tiukkaa näyttöä. Tällaisia numeroita kutsutaan epävirallisesti "Lichrel-numeroiden ehdokkaiksi". Muutamat ensimmäiset ehdokkaat Lychrel-numeroihin ovat sekvenssi A023108 OEIS : ssä :

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

Lihavoidut numerot ovat Lychrel-peruslukuja (katso alla ). Jason Doucetten, Jan Petersin ja Benjamin Despresin tietokoneohjelmat löysivät muita Lishrel-ehdokkaita. Lisäksi Benjamin Despres tunnisti kaikki Lichrel-perusluvut alle 17 numerolla [6] . Wade VanLandinghamin sivusto sisältää luettelot Lychrel-perusnumeroista jokaiselle numeropituudelle. [7]

John Walkerin alun perin kehittämää raakaa voimaa on parannettu iteraatiokäyttäytymisen hyödyntämiseksi. Esimerkiksi Won Suiten luoma ohjelma tallentaa vain ensimmäiset ja viimeiset numerot kustakin iteraatiosta, jolloin voit testata digitaalisia kuvioita miljoonien iteraatioiden aikana tarvitsematta tallentaa jokaista iteraatiota tiedostoon [8] . Mutta toistaiseksi ei ole keksitty algoritmia , joka ohittaisi iteratiivisen prosessin.

Aiheeseen liittyvät määritelmät

Jason Doucette keksi termin lanka tai lanka ( englanniksi lanka ), joka tarkoittaa alkuperäisen luvun iteraatioiden tuloksena saatua numerosarjaa . Perusluku ( eng. siemen ) ja siihen liittyvät ( eng. kin ) -luvut suppenevat yhteen virraan. Virta ei sisällä alkuperäistä peruslukua tai sen suhteellista , vaan vain numerot, jotka ovat yhteisiä molemmille, kun ne konvergoivat.

Perusluvut ovat Lichrel -lukujen osasarja, toisin sanoen pienin luku jokaisesta virrasta, joka ei tuota palindromia. Perusnumero voi itsessään olla palindromi. Kolme ensimmäistä esimerkkiä on lihavoitu yllä olevassa luettelossa.

Liittyvät luvut ovat Lichrel-lukujen osajoukko, joka sisältää kaikki virran numerot peruslukua lukuun ottamatta tai minkä tahansa luvun, joka liittyy annettuun virtaan yhden iteraation jälkeen. Koji Yamashita otti termin käyttöön vuonna 1997.

Rele numero 196

Koska numero 196 on Lichrel-lukujen pienin ehdokas, se on saanut eniten huomiota.

John Walker aloitti 196-viestin 12. elokuuta 1987 Sun - työasemalla 3/260. Hän kirjoitti C -ohjelman , joka toistaa "käännä ja lisää" ja tarkistaa palindromin jokaisen vaiheen jälkeen. Ohjelma oli käynnissä taustalla alhaisella prioriteetilla. Hän tallensi iterointitulokset tiedostoon kahden tunnin välein ja järjestelmän sammuttamisen yhteydessä ja kirjasi siihen mennessä saavutetun toiston määrän ja iterointinumeron. Se käynnistyi automaattisesti uudelleen viimeisestä tarkistuspisteestä aina, kun tietokone käynnistettiin. Se toimi melkein kolme vuotta ja pysähtyi sitten (ohjelmoidun mukaisesti) 24. toukokuuta 1990 ja viesti:

Pysähdyspaikka passissa 2 415 836 on saavutettu. Numero sisältää 1 000 000 numeroa. Alkuperäinen teksti (englanniksi)[ näytäpiilottaa] Pysähdyspiste saavutettiin tiellä 2 415 836.
Numero sisältää 1 000 000 numeroa.

196 kasvoi miljoonaan numeroon 2 415 836 iteroinnin jälkeen saavuttamatta palindromia. Walker julkaisi havaintonsa verkossa viimeisen tarkistuspisteen yhteydessä ja kehotti muita jatkamaan hakuaan viimeisimmän saavutetun numeron perusteella.

Vuonna 1995 Tim Irwin käytti noiden vuosien supertietokonetta ja saavutti kahden miljoonan numeron rajan vain kolmessa kuukaudessa, mutta ei löytänyt palindromia. Jason Doucette liittyi sitten tähän määrälliseen suuntaan ja saavutti 12,5 miljoonaa lukua toukokuussa 2000. Wade VanLandingham saavutti Jason Doucetten ohjelmaa käyttäen 13 miljoonaa numeroa, mikä julkaistiin [9] kanadalaisessa lapsille suunnatussa tiedelehdessä Yes Mag . Kesäkuusta 2000 lähtien Wade VanLendingham on jatkanut lipun kantamista käyttämällä eri harrastajien kirjoittamia ohjelmia. 1. toukokuuta 2006 mennessä VanLendingham saavutti 300 miljoonan numeron rajan (miljoonaa numeroa 5-7 päivän välein). Hajautetun laskennan avulla Romain Dolbeau ( fr. Romain Dolbeau ) teki vuonna 2011 miljardi iteraatiota ja sai 413 930 770 numerosta koostuvan luvun [10] , heinäkuussa 2012 hänen laskelmat saavuttivat 600 miljoonan numeron luvun ja helmikuussa 2015 numeron. ylitti miljardin [11] , mutta palindromia ei koskaan löydetty.

Muita saman haun kohteena olevia Lishrel-ehdokkaita ovat 879, 1997, 7059 ja muut perusluvut: niitä on jäljitetty miljoonien ja kymmenien miljoonien iteraatioiden aikana ilman palindromia [12] [13] .

Muistiinpanot

↑ Anton Stefanov (stefanov94). Palindromien lykkääminen uudelle vuodelle (venäjäksi) // Habr: sivusto. - 2021. - 5. tammikuuta. Arkistoitu alkuperäisestä 7. tammikuuta 2021.
↑ Dmitri Maslov. Löytyi pienin viivästetty palindromi vaiheelle 289 (venäjä) // iLWN-projekti: sivusto. - 2021 - 14. lokakuuta. Arkistoitu alkuperäisestä 6. marraskuuta 2021.
↑ Dmitri Maslov. Uusi viivästettyjen palindromien maailmanennätys on asetettu: 293 iteraatiota! (venäjä) // iLWN: sivusto. - 2021 - 14. joulukuuta. Arkistoitu alkuperäisestä 6. marraskuuta 2021.
↑ Arkistoitu kopio . Haettu 29. toukokuuta 2006. Arkistoitu alkuperäisestä 16. toukokuuta 2006. (määrätön)
↑ Palindromeihin johtavat numeroiden käännössummat (linkki ei ole käytettävissä) . Käyttöpäivä: 4. tammikuuta 2011. Arkistoitu alkuperäisestä 6. helmikuuta 2010. (määrätön)
↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 4. tammikuuta 2011. Arkistoitu alkuperäisestä 18. maaliskuuta 2010. (määrätön)
↑ Arkistoitu kopio (linkki ei saatavilla) . Käyttöpäivä: 4. tammikuuta 2011. Arkistoitu alkuperäisestä 26. heinäkuuta 2010. (määrätön)
↑ Arkistoitu kopio . Haettu 15. lokakuuta 2006. Arkistoitu alkuperäisestä 15. lokakuuta 2006. (määrätön)
↑ Tulossa vai menossa? (Englanti)
↑ Käänteisen ja lisäämisen algoritmin p196_mpi toteutus Palindromi-tehtävälle . Käyttöpäivä: 17. tammikuuta 2015. Arkistoitu alkuperäisestä 19. huhtikuuta 2015. (määrätön)
↑ p196_mpi -sivu . Käyttöpäivä: 17. tammikuuta 2015. Arkistoitu alkuperäisestä 11. helmikuuta 2015. (määrätön)
↑ Lychrel Records . Arkistoitu alkuperäisestä 21. lokakuuta 2006. (määrätön)
↑ Löytää palindromi 196 - iLWN - projekti . Haettu 6. marraskuuta 2021. Arkistoitu alkuperäisestä 6. marraskuuta 2021. (määrätön)

Linkit

John Walker (englanniksi) - kolme vuotta tietojenkäsittelyä.
Tim Irwin (englanti) - noin kaksi kuukautta tietojenkäsittelyä.
Jason Doucette - World Records (englanniksi) - "Numeron 196 viesti", viivästyneimmät palindromit.
Benjamin Despres (Englanti) .
196 ja muut Lichrel-numerot. Wade VanLandinghamin verkkosivusto .
Weisstein, Eric W. 196-Algoritm (englanniksi) Wolfram MathWorld -verkkosivustolla .
Weisstein, Eric W. Lychrel Number (englanniksi) Wolfram MathWorld -verkkosivustolla .
Weisstein, Eric W. Palindromic Number Conjecture (englanniksi) Wolfram MathWorld -verkkosivustolla .
Weisstein, Eric W. Reverse-Then-Add Sequence (englanniksi) Wolfram MathWorld -verkkosivustolla .
MathPages - numeron siirtosumma, joka johtaa palindromeihin
Tarinoita matemaatikoista. Clara Ziskin. Ongelman maininta venäjänkielisessä kirjallisuudessa.
Kaikki tunnetut viivästyneet palindromit ovat Dmitry Maslovin MDPN-projektista.
Viivästynyt palindromitarkastus – Dmitry Maslov, MDPN-projekti.