LYCHREL Numer – Wikipedia

Posted on by
before-content-x4

I Nazwa Lychrel jest liczbą naturalną, która nie może utworzyć liczby palindromu, gdy podlega iteracyjnego procesu, który polega na dodaniu go do uformowanej liczby odwrócenia swoich liczb w bazie 10. Nazwa „Lychrel” została wymyślona przez Wade Vanlandham: to jest prawie anagramem imienia jego narzeczonej, Cheryl. Liczby Lychrela to liczby teoretyczne. Nie wiemy, chociaż podejrzewa się wiele liczb. Najmniejsza liczba podejrzana o bycie Lychrel to 196.

after-content-x4

Albo N Niezerowa naturalna liczba całkowita, mamy:

N = A P × dziesięć P + A P – Pierwszy × dziesięć P – Pierwszy + . . . + A Pierwszy × dziesięć + A 0 = ∑ I = 0 P A I × dziesięć I {DisplayStyle n = a_ {p} Times 10^{p}+a_ {p-1} Times 10^{p-1}+…+a_ {1} Times 10+a_ {0} = sum _ {i = 0}^{P} A_ {i} Times 10^{i}}

, gdzie każdy

A I {DisplayStyle A_ {i}}

wyznacza liczbę od 0 do 9 (liczby jednostek, dziesiątki, setki …) i

A P ≠ 0 {DisplayStyle A_ {P} NEQ 0}

.

Wzywamy przewrócone N numer

N ′ = A 0 × dziesięć P + A Pierwszy × dziesięć P – Pierwszy + . . . + A P – Pierwszy × dziesięć + A P = ∑ I = 0 P A P – I × dziesięć I {DisplayStyle N ‘= A_ {0} Times 10^{P}+A_ {1} Times 10^{P-1}+…+A_ {P-1} Times 10+A_ {p} = sum _ { i = 0}^{p} a_ {p-i} Times 10^{i}}

(Notacja

after-content-x4
N ′ {DisplayStyle N ‘}

jest tutaj arbitralne).

Dla każdej naturalnej liczby całkowitej

N 0 {DisplayStyle N_ {0}}

nie palindrom, to znaczy takie

N 0 ≠ N 0 ′ {DisplayStyle N_ {0} neq n ‘_ {0}}

, wykonujemy następujący algorytm:

N Pierwszy = N 0 + N 0 ′ {DisplayStyle n_ {1} = n_ {0}+n ‘_ {0}}

N 2 = N Pierwszy + N Pierwszy ′ {DisplayStyle n_ {2} = n_ {1}+n_ {1} ‘}

… {DisplayStyle Dots}

N P = N P – Pierwszy + ( N P – Pierwszy ) ′ {DisplayStyle n_ {p} = n_ {p-1}+(n_ {p-1}) ‘}

… {DisplayStyle Dots}

Zatrzymujemy iterację w J -Me si si si si

N J = N J ′ {DisplayStyle n_ {j} = n_ {j} ‘}

.

Mówi się, że liczba jest Lychrel, jeśli to zatrzymanie nigdy się nie wydarzy, tj. Jeśli algorytm wytwarza nieskończony apartament całych niealindromów lub na każdym etapie,

N J ≠ N J ′ {DisplayStyle N_ {J} NEQ N_ {J} ‘}

.

Uogólnienie na wszelkie pozytywne podstawy [[[ modyfikator |. Modyfikator i kod ]

Albo N Naturalna liczba całkowita w bazie B> 1 W całości mamy:

N B = A P B P + A P – Pierwszy B P – Pierwszy + . . . + A Pierwszy B + A 0 = ∑ I = 0 P A I B I {DisplayStyle n_ {b} = a_ {p} b^{p}+a_ {p-1} b^{p-1}+…+a_ {1} b+a_ {0} = sum _ {i = 0}^{p} a_ {i} b^{i}}

, Lub

A P ≠ 0 {DisplayStyle A_ {P} NEQ 0}

I

0 ≤ A I < B {DisplayStyle 0leq a_ {i}

.

Należy wtedy

N B ′ = A 0 B P + A Pierwszy B P – Pierwszy + . . . + A P – Pierwszy B + A P = ∑ I = 0 P A P – I B I {DisplayStyle n ‘_ {b} = a_ {0} b^{p}+a_ {1} b^{p-1}+…+a_ {p-1} b+a_ {p} = sum _ {i = 0}^{p} a_ {p-i} b^{i}}

. W zależności od tego samego procesu obliczamy:

( N B ) Pierwszy = ( N B ) 0 + ( N B ′ ) 0 {DisplayStyle (n_ {b}) _ {1} = (n_ {b}) _ {0}+(n ‘_ {b}) _ {0}}}

( N B ) 2 = ( N B ) Pierwszy + ( N B ′ ) Pierwszy {DisplayStyle (n_ {b}) _ {2} = (n_ {b}) _ {1}+(n ‘_ {b}) _ {1}}}

… {DisplayStyle Dots}

( N B ) P = ( N B ) P – Pierwszy + ( N B ′ ) P – Pierwszy {DisplayStyle (n_ {b}) _ {p} = (n_ {b}) _ {p-1}+(n ‘_ {b}) _ {p-1}}}}

Imię N Mówi się, że jest Lychrel w bazie B Jeśli algorytm wytwarza nieskończoną sekwencję braku palindroma w zasadzie B W tj. Jeśli na każdym etapie,

( N B ) J ≠ ( N B ′ ) J {displayStyle (n_ {b}) _ {j} neq (n ‘_ {b}) _ {j}}

.

Proces iteracyjny: inwersja i dodanie [[[ modyfikator |. Modyfikator i kod ]

Z początkowej liczby w bazie dziesiętnej tworzymy sumę tego ostatniego i jej lustro (to znaczy, że kolejność liczb jest wyłączona). Na przykład dla 124: Tworzymy 124 + 421 = 545. Jeśli ta nowa liczba jest palindromem, liczba początkowa nie jest liczbą Lychrel. Jeśli tak nie jest, początkowa liczba jest nadal kandydatem do pochodzi z Lychrel. Następnie zaczynamy od nowa od utworzonego ostatniego numeru. Możemy zauważyć, że wszystkie liczby jednej i dwóch postaci prowadzą do palindromu. 80% liczb poniżej 10 000 prowadzi do palindromu w mniej niż 4 iteracjach, a około 90% w mniej niż 7.

Oto kilka przykładów liczb, które nie są Lychrel:

  • 124 wymaga iteracji: 124 + 421 = 545
  • 59 wymaga 3 iteracji:
    59 → 59 + 95 = 154
    154 → 154 + 451 = 605
    605 → 605 + 506 = 1 111
  • 89 wymaga 24 iteracji [[[ Pierwszy ] .
  • 139684416605065033860 wymaga 289 iteracji, aby doprowadzić do palindromu 142 cyfr, co stanowi obecny rekord dla najbardziej opóźnionego palindromu. Został znaleziony przez algorytm Anton Stefanov . .

Zauważamy, że w przypadku niektórych liczb proces ten nie wydaje się przestać. Dotyczy to w szczególności 196, co jest najmniejszym z tych liczb (i dlatego jesteśmy tym zainteresowani). Problem polega na tym, że nie możemy wykazać, że dla tych liczb proces nie kończy się. Przynajmniej zależy to od podstawy, ponieważ dla niektórych podstaw jest to możliwe [[[ 2 ] . Tak więc w świetle wielu przeprowadzonych iteracji przypuszczamy, że 196 i wszystkie poniższe liczby pochodzą z Lychrel.

Lista [[[ 3 ] Z pierwszej liczby kandydatów Lychrel to:
196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1,495, 1 497, 1 585, 1 587, 1 675, 1 677, 1 765, 1,767, 1,855, 1 585, 1,587, 1 675, 1 675, 1 675, 1997…
Programy Jasona Doucette, Ian Peters i Benjamin Despres znaleźli wielu innych kandydatów. Rzeczywiście, program Benjamina Despres zidentyfikował wszystkich kandydatów o mniej niż 17 cyfr [[[ 4 ] . Witryna Wade Vanlandham wymienia liczbę kandydatów według liczby liczb [[[ 4 ] .

Metoda brutalnej siły początkowo stosowana przez Johna Walkera została ponownie wprowadzona w celu skorzystania z specyfiki procesu. Na przykład, Vaughn Suite zaprojektował program, który utrzymuje tylko pierwszą i ostatnią liczbę przy każdej iteracji, można zatem sprawdzić, czy liczba (nie) zbiega się (nie) do palindromu bez konieczności zapamiętywania liczby w pamięci [[[ 5 ] . Ale jak dotąd nie opracowano algorytmu, aby ominąć proces inwersji i dodawania.

Schemat wątków utworzony przez nasiona 196. Podświetlone liczby to liczby związane z 196. Liczby w prostokącie to liczby drutu.

Termin „wątek” ( nitka W języku angielskim) wprowadzony przez Jasona Doucette odpowiada serii liczb uzyskanych przez proces.

Ziarno ”( nasionko W języku angielskim) jest najmniejszą liczbą powodującą nie zakończenie drutu: jest to zatem podzbiór liczby Lychrel. Nasiona, podobnie jak liczba Lychrel, może być palindromem. Zatem z każdym wątkiem odpowiada pojedynczej nasionowi.

Z nasioną kojarzymy jego liczby powiązany (Kin in English), termin wprowadzony przez Koji Yamashity, są to liczby, które zbiegną się w kierunku przewodu nasiennego lub które już należą do tego drutu. Jest to również podzbiór liczby Lychrel. Zatem ziarno i jego powiązane liczby zbieżą się w tym samym wątku.

Należy zauważyć, że rozważania te są tylko teoretyczne, ponieważ nie znaleźliśmy jeszcze wielu Lychrel.

Pierwsze potencjalne nasiona to: 196, 879, 1997… patrz apartament A063048 oka

196 Bycie najmniejszym z kandydatów, którzy są liczbą Lychrel, to on przyciągnął największą uwagę.
John Walker rozpoczął badania Na platformie Sun 3/260 z programem napisanym w C, który przeprowadził iteracje i który sprawdził, czy liczba była palindromem [[[ 6 ] . Program chodził w tle z niskim priorytetem i tworzył raport co dwie godziny, rejestrując ostatni wynik wyginięcia systemu. Trwało to prawie 3 lata i zakończyło się (zgodnie z pytaniem) Z następującą wiadomość:

Punkt zatrzymania osiągnął 2 415 836 iteracji.
Liczba ma 1 000 000 danych.

196 osiągnął zatem kilka milionów liczb po 2 415 836 iteracji bez osiągnięcia palindromu. Walker opublikował swoje badania nad tym ostatnim raportem, zapraszając innych ludzi do ponownego rozpoczęcia badań, pozostawiając ostatni znaleziony numer. W 1995 r. Tim Irvin użył supermarketu i osiągnął kilka 2 milionów danych w ciągu zaledwie 3 miesięcy bez znalezienia palindromu. Jason Doucette kontynuował premierę i osiągnął 12,5 miliona liczb w . Wade Vanlandingham wykorzystał program Jasona Doucette, aby osiągnąć 13 milionów danych, rekord opublikowany w Tak, mag , Magazyn dla dzieci w Kanadzie. . , Vanlandingham osiągnął 300 milionów liczb (ze średnio milionami liczb co 5 lub 7 dni). W 2011 r. Romain Dolbeau zastosował obliczenia rozproszone [[[ 7 ] Osiągnąć miliard iteracji lub liczbę 413 930 770 liczb. W , jego obliczenia osiągnęły miliard danych [[[ 8 ] . Mimo to nie znaleziono palindromu.

Oczywiście inni kandydaci, tacy jak 879, 1997 i 7059, byli również szczegółowo testowani tą samą brutalną metodą, osiągając również kilka milionów iteracji bez znalezienia najmniejszego palindromu.

Operacje inwersji liczb i suma nie są specyficzne dla podstawy 10, możliwe jest poszukiwanie liczby Lychrel w innych podstawach. W ten sposób udowodniono, że w bazie 2 liczba 10110 (22 w bazie 10) jest liczbą Lychrel [[[ 6 ] . Istnienie liczb Lychrel zostało udowodnione, gdy podstawa jest mocą 2 lub jeśli jest to 11, 17, 20 lub 26 [[[ 6 ] .

after-content-x4