Suma Kwadratów Cyfr

Treść

Polski matematyk H. Steinhausa przedstawił kiedyś tezę, że jeśli dla liczby nonstop będziemy sumować kwadraty jej cyfr i ponownie wykonywać tę operację. To zawsze na koniec otrzymamy 1 lub 4. Jednak czy istnieje taka liczba, że nigdy nie osiągniemy 1, ani 4 ?

Przykłady

Weźmy przykładowo liczbę 42. Suma jej cyfr to 4² + 2² = 20. Powtarzając proces otrzymujemy: 2² + 0² = 4. Na końcu zgodnie z przypuszczeniami otrzymaliśmy 4.

Jednak już dla liczby o zaledwie jeden więcej potrzebnych jest, aż osiem przekształceń. Można się o tym przekonać zapoznając się z poniższą tabelką:

Czy zawsze?

Czy można udowodnić, że sumując w ten sposób cyfry zawsze osiągniemy 1 lub 4? Otóż można to udowodnić w sposób nie bezpośredni. Najpierw zastanówmy się w jakich przedziałach jest szansa, że liczby rosną i maleją, a czy jest taki przedział, że zawsze maleją. W tym celu będziemy brać coraz to dłuższe liczby złożone tylko z cyfr 9, ponieważ sumując kwadraty 9 uzyskamy największą możliwą sumę cyfr. W przypadku samej 9 suma urośnie do 81. Z kolei dla 99 suma ponownie urośnie maksymalnie do 162. Jednak dla kolejnych wartości tj. 999 otrzymamy 243. Liczba cyfr nie wzrosła i gwarantowane jest to, że zacznie maleć dalej. Dla większych wartości np. 9999, 99999, aż do 999999999999 zawsze otrzymamy liczbę trzycyfrową.

Oznacza to, że nieważne jak dużą liczbę weźmiemy bardzo szybko wrócimy do liczb trzycyfrowych. Dalej zachowanie wartości nie jest łatwe do przewidzenia, bo jak sprawdziliśmy dla różnych wartości wartość może zmaleć do jednej cyfry, albo podnieść się z powrotem do trzycyfrowe. Jednak jeśli sprawdzimy czy wszystkie liczby trzycyfrowe spełniają podaną hipoteze to jest gwarantowane, że dla dowolnej liczby naturalnej doprowadzimy do 1 lub 4.

Dodatkowe uwagi

Jednak dlaczego sumowanie kwadratów cyfr kończy się na 1 i 4? Dla 1 idea zatrzymania jest trywialna, ponieważ zawsze sumując kwadraty cyfr 1 otrzymamy 1, więc zatrzymanie jest tutaj jak najbardziej słuczne. Z kolei 4 podniesione do kwadratu to 16, więc istnieje możliwość "rozwinięcia" tej liczby. Problem jednak powstaje dalej, ponieważ kolejne przekształcenia prowadzą do następującego ciągu liczb (4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, ...). Poszukiwanie ostatniej wartości jest niemożliwe, bo ciąg się zapętla.

Implementacja

Sprawdzanie każdej liczby począwszy od jednocyfrowej, przez dwucyfrową, aż do trzycyfrowej może być zadaniem bardzo czasochłonnym, więc najlepiej napisać algorytm, który sprawdzi dany zakres za nas.

1. bool sumujKwadratyCyfr(int a) {
2.   while (a != 1 && a != 4) {
3.     int s = 0;
4.     while (a > 0) {
5.       int c = a % 10;
6.       s += c * c;
7.       a /= 10;
8.     }
9.     a = s;
10.   }
11.   return true;
12. }

Przedstawiony kod składa się z nieskończonej pętli, która w każdej iteracji oblicza sumę kwadratów cyfr. Po zakończeniu działania pętli zwracana jest wartość prawda. Jednak gdzie fałsz? Otóż, żeby dowieść, że nie wszystkie liczby kończą się na 1 lub 4 to należałoby dowieść, że jest jakaś grupa liczb, która się zapętla. Tu jednak możemy przyjąć, że jeśli pętla będzie obliczać bardzo długo to znaleźliśmy wartość, która nie jest sprowadzalna do podanych w hipotezie wartości.

Testowanie funkcji

W celu sprawdzenia pojedynczej dowolnej liczby można skorzystać z poniższego fragmentu kodu. Wczyta on od użytkownika liczbę do sprawdzenia i wypisze czy liczba spełnia warunki.

1. int main() {
2.   int a;
3.   cout << "Podaj liczbe do sprawdzenia:\n a = ";
4.   cin >> a;
5.   cout << (sumujKwadratyCyfr(a) ? "TAK" : "NIE");
6.   system("pause");
7.   return 0;

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję sprawdzZakres(), która będzie sprawdzać pewny zakres [1, max] w poszukiwaniu wartości, która nie spełnia warunków hipotezy Steinhausa. Nie korzystaj z napisanej funkcji do sprawdzania czy dana liczba spełnia warunki. Wskazówka: skorzystaj z dodatkowej tablicy, aby przyśpieszyć proces. Funkcja powinna zwrócić wartość logiczną czy wszystkie wartości z zakresu spełniają kryteria.

Zadanie 2

Porównaj ilość operacji potrzebnych do sprawdzania danego zakresu przy użyciu funkcja sprawdzZakres() oraz pętli for korzystającej z funkcji sumujKwadratyCyfr(). Określ operację dominującą i wyznacz przybliżoną złożoność.

Dodatkowo program powinien wypisać na ekran tabelkę w której zostaną zebrane dane do porównania:

1. n        for        sprawdzZakres()
2. 10^1     58         58
3. 10^2     715        222
4. 10^3     8461       2097
5. 10^4     90921      20199
6. 10^5     933232     200284

• Kod źródłowy Zadanie 1
• Kod źródłowy Zadanie 2