Liczby Lychrela

Definicja

W celu sprawdzenia czy liczba a jest liczbą Lychrela należy obliczyć f(a) = a + wspak(a), a następnie sprawdzić czy liczba jest palindromem. Jeśli liczba jest palindromem to znaczy, że nie jest to liczba Lychrela. W przeciwnym razie należy sprawdzić czy f(a) jest liczbą Lychrela.

Analiza

Liczby Lychrela to niezwykle trudne liczby do udowodnienia, że są nimi, ponieważ poszukiwania czy f(a) kiedyś stanie się palindromem może odbywać się w nieskończoność. Z tego względu poszukiwania należy ograniczyć do pewnej wartości. Pozwala to określić, że dana liczba jest liczbą Lychrela w pewnym zakresie. Jest to szczególnie problematyczne dla komputerów, których typy danych mogą przyjmować tylko liczby z określonego zakresy, a więc nie mogą wykonywać sprawdzeń w nieskończoność.

Ciąg liczb

Oto ciąg pierwszych 10 liczb Lychrela: 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, ..

Implementacja

Próba wypisania ciągu liczb Lychrela przy pomocy przedstawionego kodu może dać niepoprawny ciąg, ponieważ zmienne mają ograniczony zakres liczb w którym nie zostaje udowodnione, że dana liczba w pewnym momencie staje się palindromiczna. Prawidłowy ciąg wypisuje skrypt napisany w języku Python, ponieważ liczby mogą w nim mieć teoretycznie nieograniczoną długosć (choć w kodzie ogranicza się ten zakres).

Funkcje pomocnicze

Przed napisanie funkcji czyLiczbaLychrera() warto przygotować kilka funkcji pomocniczych do obliczania liczby wspak, sprawdzania czy liczba jest palindromem oraz czy dwie liczby można dodać.

Liczba wspak

Do generowania liczby zapisanej wspak służy funkcja o wspomnianej nazwie. Jako argument potrzebuje jedynie liczby do zapisania wspak. Przykładowo dla 123 zwróci 321.

1. def wspak(a):
2.   wynik = 0
3.   while (a > 0):
4.     if (wynik > MAX_SIZE // 10):
5.       return 0
6.     wynik *= 10
7.     wynik += a % 10
8.     a //= 10
9.   return wynik

Palindrom

W celu sprawdzenia czy liczba jest palindromiczna należy skorzystać z funkcji czyPalindromiczna(), która przyjmuje jedną liczbę a. W wyniku otrzymuje się wartość logiczną. Więcej informacji o palindromach można znaleźć tutaj.

1. def czyPalindromiczna(a):
2.   dl = int(math.log10(a)) + 1
3.   wybierz = int(math.pow(10, dl // 2))
4.   prawa = a % wybierz
5.   lewa = a // wybierz
6.   if (dl % 2 == 1):
7.     lewa //= 10
8.   return wspak(lewa) == prawa

Liczba jest dzielona na lewą i prawą część. Środkowa cyfra jest ignorowana, ponieważ nie ma znaczenia na wynik. Jeśli liczby nie można zapisać wspak to funkcja zwraca 0.

Dodawanie

Przekroczenie zakresu typu danych może doprowadzić do niespodziewanych wyników. Z tego powodu należy przed dodaniem dwóćh liczb upewnić się, że takie dodawanie nie przekroczy zakresu. Ponadto jest to funkcja, która pozwoli ograniczyć zakres poszukiwań, aby nie szukać odpowiedzi w nieskończoność.

1. def czyMoznaDodac(a, b):
2.   max = MAX_SIZE - a
3.   return (max > b)

Od maksymalnego zakresu odejmowana jest jedna z liczb i należy sprawdzić czy uzyskany wynik jest większy lub równy drugiej liczby. Więcej informacji o dodawaniu w pewnym zakresie można znaleźć tutaj.

Funkcja główna

Funkcja czyLiczbaLychrera() zwraca wynik czy dana liczba a jest liczbą Lychrela.

1. def czyLiczbaLychrera(a):
2.   b = wspak(a)
3.   if (not czyMoznaDodac(a, b) or b == 0):
4.     return True
5.   a += b
6.   if (czyPalindromiczna(a)):
7.     return False
8.   return czyLiczbaLychrera(a)

Zgodnie z definicją funkcja najpierw próbuje dodać a oraz b = wspak(a). Jeśli liczb nie można dodać to możliwe, że jest to liczba Lychrela. Poszukiwania kończą się również jeśli liczba zapisana wspak to 0 (jest to wartość zwracana, gdy nie można zapisać liczby wspak). Jeśli jednak żaden z warunków nie jest spełniony to liczby zostają dodane i sprawdzane jest czy wynik jest palindromem. Jeśli jest to znaczy, że początkowa liczba na pewno nie jest liczbą Lychrela. W przeciwnym razie należy rekurencyjnie sprawdzić czy suma jest liczbą Lychrela i zwrócić wynik takiego wywołania.

W języku Python teoretycznie nie istnieje ograniczenie zakresu przechowywanych liczb. Aby zapobiec wyszukiwaniu rozwiązania w nieskończoność należy ograniczenie ustalić samemu np.:

1. MAX_SIZE = math.pow(10, 100)

Testowanie funkcji

Do przetestowania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

1. a = int(input("Podaj liczbe do sprawdzenia\n a = "))
2. wynik = czyLiczbaLychrera(a)
3. print(str(a) + ("" if wynik else " nie") + " jest")

• Kod źródłowy Implementacja