Ostrzegam lojalnie: to jest dość długi wpis o dodawaniu i potęgowaniu. Jeżeli masz uczulenie na dodawanie i potęgowanie, przed lekturą posmaruj się jakąś antyhistaminą albo po prostu czytaj z zamkniętymi oczyma 😉
Jeżeli ktoś jeszcze pamięta niedawny wpis o rekurencyjnym sumowaniu kwadratów cyfr liczb naturalnych, z pewnością ucieszy się[citation needed], że temat można potraktować szerzej. Zamiast bowiem ograniczać się do kwadratów, można sobie zadać pytanie: a co z wyższymi potęgami?
Przy okazji takich rozmyślań poćwiczymy sobie też programowanie w Pythonie. Ale to za chwilę. Najpierw przypomnę Czytelnikowi o sssso właśśśśsiwie chozzzzzi.
Chodzi o to, że bierzemy dowolną liczbę naturalną, następnie podnosimy każdą jej cyfrę do kwadratu, kwadraty sumujemy, a wynik tego sumowania poddajemy dokładnie tej samej operacji. Czyli: sumujemy kwadraty cyfr. I znów, i jeszcze raz. W efekcie albo dostaniemy jedynkę (która już pozostanie jedynką), albo wpadniemy w pętlę 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4 => 16 => i tak w kółko.
Innej możliwości nie ma.
Ale skąd właściwie wiemy, że zawsze wpadniemy w pętlę niezależnie od tego, od jak wielkiej liczby zaczniemy?
A no stąd, że dla dowolnej liczby \(n\)-cyfrowej, suma kwadratów cyfr może wynieść maksymalnie \(n*9^2\) - i nastąpi to tylko w sytuacji, kiedy liczba będzie się składać z samych dziewiątek. W każdym innym przypadku suma kwadratów będzie mniejsza.
Innymi słowy dołożenie kolejnej cyfry zwiększy sumę kwadratów o nie więcej, niż 81, za to samą liczbę zwiększy co najmniej dziesięciokrotnie. Ponieważ sumowanie nie ma szans w wyścigach z mnożeniem, nigdy nie wyjdziemy powyżej liczb trzycyfrowych. Jeżeli bowiem weźmiemy liczbę czterocyfrową, nawet największą możliwą, to i tak suma kwadratów jej cyfr wyniesie zaledwie \(4*9^2=324\).
Skoro więc jesteśmy ograniczeni od góry, to prędzej czy później trafimy na taką liczbę, która już wcześniej mieliśmy - i wpadniemy w cykl.
Jaki konkretnie będzie to cykl, a także ile różnych cykli jest możliwych - to już inna para kaloszy. Ale widzimy, że cykl jest gwarantowany jak śmierć i podatki.
A jeżeli weźmiemy trzecie potęgi zamiast drugich?
Rozumowanie jest identyczne! \(9^3=243\) - o tyle maksymalnie wzrośnie suma kwadratów cyfr liczby, do której dołożymy jedną cyfrę, a wartość tej liczby wzrośnie co najmniej dziesięciokrotnie.
A czwarte potęgi? A siódme?
Nie ma znaczenia, które potęgi będziemy sumować, za każdym razem będzie tak, że kolejny wyraz będzie szedł w dół, aż dojdziemy do pewnej minimalnej liczby cyfr (większej dla większych wykładników, ale zawsze skończonej), powyżej której już nie wyskoczymy. A skoro jest limit, to prędzej czy później pojawi się pętla.
Jeżeli, Czytelniku, zgadzasz się z powyższymi rozważaniami (tak, wiem, rasowy matematyk pewnie już by eksplodował z nerwów, za dużo tu dłużyzn i opisów przyrody), to zerknijmy sobie teraz na konkrety.
Najpierw napiszemy sobie prościutką funkcję, która dla zadanej liczby x i wykładnika n zwróci sumę n-tych potęg cyfr tej liczby:
def suma_poteg_cyfr(liczba, wykladnik):
suma = 0
while liczba > 0:
suma += (liczba % 10) ** wykladnik
liczba = liczba // 10
return(suma)
Dla niewtajemniczonych: % to w Pythonie reszta z dzielenia, // to dzielenie całkowite (z zaokrągleniem w dół do najbliższej całości), wreszcie ** to operator potęgowania.
Sprawdźmy, czy nasza funkcja działa:
print(suma_poteg_cyfr(12, 2))
print(suma_poteg_cyfr(24, 3))
print(suma_poteg_cyfr(578, 4))
5
72
7122
Działa!
Lecimy dalej. Skoro umiemy policzyć sumę n-tych potęg cyfr zadanej liczby, spróbujmy teraz nakarmić węża jego własnym ogonem, czyli wrzucić tę sumę na wejście tej samej funkcji i robić to tak długo, aż trafimy na powtórzenie:
def lista_sum(liczba, wykladnik):
sumy = []
while True:
suma = suma_poteg_cyfr(liczba, wykladnik)
if suma in sumy:
sumy.append(suma)
return(sumy)
sumy.append(suma)
liczba = suma
W ten sposób wiemy, która suma spowodowała wpadnięcie w pętlę – będzie to jedyny element listy, który pojawi się w niej dwukrotnie. Raz gdzieś „w środku” i raz na samym końcu.
print(lista_sum(12, 2))
print(lista_sum(24, 3))
print(lista_sum(578, 4))
[5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
[72, 351, 153, 153]
[7122, 2434, 609, 7857, 9523, 7283, 6594, 8738, 10674, 3954, 7523, 3123, 179, 8963, 12034, 354, 962, 7873, 8979, 19619, 14420, 529, 7202, 2433, 434, 593, 7267, 6114, 1554, 1507, 3027, 2498, 10929, 13139, 6725, 4338, 4514, 1138, 4179, 9219, 13139]
Pytanie - co dalej? Jak wykorzystać to narzędzie? Co ciekawego można z niego wycisnąć?
Możemy na przykład spróbować policzyć długość cyklu w ciągu sum, oczywiście przy założeniu, że ów ciąg był wygenerowany powyższą funkcją (a więc, ostatni element listy jest jedynym, który się powtarza):
def dlugosc_cyklu(sumy):
return(len(sumy) - sumy.index(sumy[-1]) - 1)
Ta króciutka, jednolinijkowa funkcja działa bardzo prosto: bierze ostatni element listy (w Pythonie ostatni element ma indeks -1), a następnie wyszukuje go na liście sum, i na koniec odejmuje pozycję znalezionego elementu od długości całej listy (i zmniejsza wynik o jeden).
Zobaczmy jak to działa na przykładzie sumy kwadratów startującej od 12:
Funkcja lista_sum zwróci nam [5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
sumy[-1] czyli ostatni element listy to 89
Wyrażenie sumy.index(89) zwróci nam indeks (pozycję) pierwszego napotkanego elementu o wartości 89, czyli 4 (w Pythonie listy numerowane są od zera).
Długość całej listy to 13
13 - 4 - 1 = 8 - i to jest dokładnie długość cyklu rozumiana jako ilość "kroków", które trzeba przejść między kolejnymi elementami cyklu, żeby natrafić na element, z którego się wystartowało.
Proste?
No, powiedzmy...
Co by tu jeszcze...
Poniższy kod zwróci nam listę długości kolejnych (coraz dłuższych) cykli znalezionych dla poszczególnych wykładników (od 2 do 10), wraz z liczbą, która do danego cyklu doprowadziła. Ale - uwaga - z pominięciem pętelek jednoelementowych (czyli na przykład ...1 => 1 => 1... czy ...153 => 153 => 153...)
print("W, L, DC")
for wykladnik in range(2, 11):
najdluzsza = 2
for liczba in range(1,10000):
sumy = lista_sum(liczba, wykladnik)
dc = dlugosc_cyklu(sumy)
if(dc > najdluzsza):
print("{}, {}, {}".format(wykladnik, liczba, dc))
najdluzsza = dc
W, L, DC
2, 2, 8
3, 4, 3
4, 2, 7
5, 2, 12
5, 3, 22
5, 7, 28
6, 2, 10
6, 3, 30
7, 2, 92
8, 2, 25
8, 3, 154
9, 2, 30
9, 3, 93
10, 2, 17
10, 3, 123
Nagłówki „W”, „L” i „DC” oznaczają, odpowiednio, „Wykładnik”, „Liczba”, „Długość Cyklu”. Wyniki są… nudne, w zasadzie. Wygląda na to, że najdłuższy cykl odnaleziono dla wykładnika równego 8 (zaczynając od trójki, natrafimy w końcu na cykl 154-elementowy). „Najbiedniej” wyglądają wykładniki 3 i 7, które mają tylko po jednym cyklu.
A gdyby sprawę jeszcze bardziej skomplikować?
Zamiast używać stałego wykładnika, uzależnijmy jego wartość od ostatniej cyfry aktualnie sprawdzanej liczby. A więc dla liczby 72 policzymy sumę kwadratów, dla 83 - trzecich potęg - a dla 98712636 - szóstych. I tak dalej.
Czy nadal gwarantowane jest wpadnięcie w ciąg cykliczny?
Na pewno! Przekształcenie w dalszym ciągu jest deterministyczne, a także istnieje maksimum, o jakie może wzrosnąć liczba po dodaniu jednej cyfry (\(9^9\)). Zweryfikujmy to dla kilku początkowych liczb.
Najpierw funkcja:
def lista_sum_dziwna(liczba):
sumy = []
while True:
wykladnik = liczba % 10
suma = suma_poteg_cyfr(liczba, wykladnik)
if suma in sumy:
sumy.append(suma)
return(sumy)
sumy.append(suma)
liczba = suma
lista_sum, jedyne „udziwnienie” to zmiana wykładnika w każdym przejściu pętli.
Wyniki?
Zaskakujące! Wygląda na to, że za każdym razem wpadamy w pętlę dwuelementową …27 => 823671 => 27…
Sprawdźmy dla pierwszej dziesiątki:
for i in range(2, 11):
print(i, lista_sum_dziwna(i))
Wynik:
2 [4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
3 [27, 823671, 27]
4 [256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
5 [3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
6 [46656, 159689, 921089528, 120039012, 100, 3, 27, 823671, 27]
7 [823543, 763, 586, 324425, 5480, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
8 [16777216, 446325, 13224, 370, 3, 27, 823671, 27]
9 [387420489, 696754035, 98925, 154023, 225, 3189, 521657901, 36, 47385, 53967, 5966760, 7, 823543, 763, 586, 324425, 5480, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10 [2, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
Dziewiątce wpadnięcie w pętlę (...27, 823671, 27...) zajęło ponad 30 kroków, ale też tam trafiła.
Sprawdźmy kilka większych liczb :
for i in range(10000, 10011):
print(i, lista_sum_dziwna(i))
Wynik:
10000 [5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10001 [2, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10002 [5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10003 [28, 16777472, 253, 160, 3, 27, 823671, 27]
10004 [257, 901796, 1227188, 39319747, 11233783, 946, 582193, 1402, 21, 3, 27, 823671, 27]
10005 [3126, 47450, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10006 [46657, 1477924, 11892, 151, 7, 823543, 763, 586, 324425, 5480, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10007 [823544, 5330, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10008 [16777217, 3574238, 23011556, 78701, 23, 35, 3368, 18469954, 19652, 147, 839928, 119654691, 42, 20, 2, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10009 [387420490, 9, 387420489, 696754035, 98925, 154023, 225, 3189, 521657901, 36, 47385, 53967, 5966760, 7, 823543, 763, 586, 324425, 5480, 4, 256, 62345, 12200, 5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
10010 [5, 3125, 3401, 8, 16777216, 446325, 13224, 370, 3, 27, 823671, 27]
To samo!
Sprawdźmy ostatni element każdej listy sum od dwóch do miliona:
for i in range(2, 1000001):
l = lista_sum_dziwna(i)[-1]
if(l not in [27, 823671]):
print(i, l)
Na wyjściu zaczęło pojawiać się całkiem sporo śmiecia! A więc 27, 823671, 27 to nie jest jedyny cykl!
Okazało się, że jeżeli ciąg sum trafi na 153, to się zapętla na 153 (pamiętamy tę liczbę z okolic początku tego wpisu, prawda?)
Ponadto okazuje się, że podobnie sytuacja wygląda z liczbami 1634 oraz 9474, których sumy czwartych potęg cyfr dają w wyniku, odpowiednio, 1634 i 9474 😉 Mamy więc odkryte trzy cykle jednoelementowe.
Coś jeszcze?
9800817 to kolejny cykl jednoelementowy (suma siódmych potęg cyfr daje tę sama liczbę)
I... w zasadzie to by było na tyle, jeśli chodzi o pierwszy milion.
Szukamy dalej?
Nieeee, nudy.
A co, jeżeli zamiast ostatniej cyfry, jako wykładnika użyjemy cyfry pierwszej?
def lista_sum_dziwna2(liczba):
sumy = []
while True:
wykladnik = liczba // 10**(int(log(liczba, 10)))
suma = suma_poteg_cyfr(liczba, wykladnik)
if suma in sumy:
sumy.append(suma)
return(sumy)
sumy.append(suma)
liczba = suma
(UWAGA! żeby to zadziałało, musimy na samym początku naszego skryptu dopisać: from math import log)
print(lista_sum_dziwna2(2))
print(lista_sum_dziwna2(3))
print(lista_sum_dziwna2(4))
print(lista_sum_dziwna2(5))
print(lista_sum_dziwna2(6))
[4, 256, 65, 62281, 308929, 2005, 29, 85, 17167841, 35, 152, 8, 16777216, 37, 370, 370]
[27, 53, 3368, 782, 2920823, 166, 13, 4, 256, 65, 62281, 308929, 2005, 29, 85, 17167841, 35, 152, 8, 16777216, 37, 370, 370]
[256, 65, 62281, 308929, 2005, 29, 85, 17167841, 35, 152, 8, 16777216, 37, 370, 370]
[3125, 161, 8, 16777216, 37, 370, 370]
[46656, 4769, 10514, 11, 2, 4, 256, 65, 62281, 308929, 2005, 29, 85, 17167841, 35, 152, 8, 16777216, 37, 370, 370]
for i in range(2, 1000):
l = lista_sum_dziwna2(i)[-1]
if(l != 370):
print(i, l)
– Liczby zaczynające się jedynką, których suma cyfr daje 10, zapętlają się na jedynce. Logiczne!
– Ponieważ istnieją liczby, których suma potęg cyfr jest liczbą zaczynającą się od 1, o sumie cyfr 10, one też skończą jako jedynka. Przykład: 1747 albo 387420490.
for i in range(2, 1000):
l = lista_sum_dziwna2(i)[-1]
if(l not in [1, 370]):
print(i, l)
317 371
371 371
A co się dzieje powyżej tysiąca?
for i in range(1000, 10000):
l = lista_sum_dziwna2(i)[-1]
if(l not in [1, 370, 371]):
print(i, l)
Jest odkrycie! Startując od 5449, trafiamy na nietrywialną pętlę:
[64222, 50944, 64222]Jest to jedyne ciekawe znalezisko poniżej 10000. Zajrzyjmy, co dzieje się między 10K a 1M:
for i in range(10000, 1000001):
l = lista_sum_dziwna2(i)[-1]
if(l not in [1, 370, 371, 64222]):
print(i, l)
Okazuje się, że bardzo dużo liczb ląduje w pętli zakończonej na 54748 lub na 50944.
54748 jest przypadkiem trywialnym (jest sumą piątych potęg swoich własnych cyfr), natomiast 50944 to pętelka dwuelementowa:
[50944, 64222, 50944]Skoro tak dobrze nam idzie, może zajrzymy w zakres 1M - 10M?
Hmmm...
for i in range(1000000, 10000001):
l = lista_sum_dziwna2(i)[-1]
if(l not in [1, 370, 371, 64222, 54748, 50944]):
print(i, l)
Cisza. A więc sześć przypadków szczególnych to wszystkie "interesujące" wydarzenia - zakładam, że ponieważ dziewiątka jest najwyższym możliwym wykładnikiem, powyżej 10M nie ma już żadnych "nowinek".
Na zakończenie jeszcze jeden eksperyment, też całkiem podobny do poprzednich. Będziemy sumować potęgi, tylko wykładnik będziemy dobierać w nieco inny sposób: największa z cyfr. A więc dla 132 będzie to \(1^3+3^3+2^3\) a dla 787 - \(7^8+8^8+7^8\). I tak dalej.
Funkcja generująca listę sum:
def lista_sum_dziwna3(liczba):
sumy = []
while True:
wykladnik = int(max(str(liczba)))
suma = suma_poteg_cyfr(liczba, wykladnik)
if suma in sumy:
sumy.append(suma)
return(sumy)
sumy.append(suma)
liczba = suma
Sprawdzamy, czy działa: print(lista_sum_dziwna3(2)).
Wynik?
O żeż...
[4, 256, 62345, 67170, 1927023, 427794804, 603132375, 1188294, 656118603, 22213252, 3529, 389393809, 1430755972, 472316293, 438154327, 23077093, 468167581, 43134628, 18601283, 35240867, 24684611, 20267778, 35751747, 2645451, 86163, 20143010, 355, 6493, 397780012, 602365627, 1743919, 815476414, 24808868, 68854272, 41455522, 11488, 33619970, 825311648, 35697028, 574042840, 23129506, 399472018, 949694653, 1184913955, 913246786, 582429556, 537838456, 41858757, 45930821, 523873682, 41403108, 16914851, 533931185, 525603518, 19635525, 403377756, 2849448, 656642889, 688304814, 52148898, 792289455, 953581731, 565937442, 442302525, 8637, 24228194, 522164042, 70666, 1663351, 110397, 427793781, 642981378, 706569588, 720271194, 468390873, 706588758, 64322116, 98267, 572070032, 1727654, 2021660, 93441, 387964461, 582691188, 802105008, 33945314, 389956952, 1310483336, 18548614, 35755747, 2723575, 1805779, 604298557, 576238426, 26364483, 20280898, 790074697, 906241639, 795278710, 644652676, 2054308, 17240194, 428298898, 1311975058, 565917760, 492189346, 919680886, 1197649555, 831393802, 655915507, 445664293, 410335633, 69294, 785181330, 39722982, 949433532, 777377952, 591161844, 534193329, 777115809, 644652165, 179475, 470342973, 468691869, 1073771667, 3856233, 18867396, 716384628, 42750819, 564207606, 1757988, 738516285, 41786917, 612685273, 26298948, 1053617298, 574042842, 23129762, 437873012, 28385733, 39729797, 1283342483, 33705700, 1729585, 565898587, 846364351, 20671268, 25901762, 439805942, 911556314, 401686265, 22272482, 22608833, 35247682, 24684867, 42809793, 949694652, 1184894784, 831213714, 22620934, 397781548, 738798112, 736583356, 26702182, 24222402, 592, 389374126, 572371543, 1824223, 16850082, 35624930, 399753332, 817226954, 574285814, 40231812, 16849827, 706549905, 829440675, 574547445, 1946997, 1212954915, 779010399, 1242988365, 668169618, 696166731, 468104565, 21048771, 28372612, 24228963, 531999276, 1214666091, 417916236, 448211829, 656381259, 545720055, 1152555, 12534, 4425, 5205, 6282, 18457344, 23135812, 17181477, 34137158, 23011302, 72, 823671, 24228451, 17299682, 959491034, 1164758564, 26813573, 24625637, 1480367, 24293731, 428076631, 25973603, 439844795, 952171553, 433653668, 22291908, 909060243, 785201013, 22939461, 785201526, 25003396, 399491188, 1430978752, 604580896, 678226606, 29260993, 1172359870, 604318753, 24690917, 825534938, 660064217, 1679864, 582409361, 533951378, 565957124, 443973824, 562818134, 35697028]
Lista jest długa. Naprawdę długa. Cykl też jest niemały:
l = lista_sum_dziwna3(2)
print(dlugosc_cyklu(l))
Wynik: 204
Nie dziwi mnie to. Ponieważ na wykładnik zawsze wybieramy maksymalną cyfrę, należy się spodziewać wysokich wykładników, a więc też dłuższych liczb, stąd też zapętlenia będą dłuższe.
Rzućmy teraz okiem na wartości, na których się zapętla. Do pierwszej setki, razem z długościami pętli:
for i in range(2, 101):
l = lista_sum_dziwna3(i)
print(i, dlugosc_cyklu(l), l[-1])
Pobieżne przejrzenie wyników mówi mi, że istnieje bardzo niewiele pętli:
- Jedna, która już znamy z przykładu z dwójką (ta na 204 elementy)
- Jedna z jedynką (przypadki trywialne, dla 10, 100 itd)
- Dwie trywialne ("jednokrokowe") pętle dla liczb 24678051 i 24678050, które są sumami ósmych potęg swoich cyfr.
Powtarzając eksperyment dla drugiej setki liczb zaobserwujemy jeszcze dodatkową trywialną pętlę dla 4150
Ciekawiej zaczyna się robić w zakresie do tysiąca:
for i in range(200, 1000):
l = lista_sum_dziwna3(i)
if(l[-1] not in [24678050, 24678051, 4150] and dlugosc_cyklu(l) != 204):
print(i, dlugosc_cyklu(l), l[-1])
Okazuje się, że istnieje pętla czteroelementowa ... - 531997741 - 857783146 - 47226373 - 1948036 - 531997741 - ...
print(lista_sum_dziwna3(349))
[387702316, 29999813, 1683919880, 1187591543, 566179904, 837565247, 30840037, 22620675, 1461924, 398022987, 1083650748, 41461572, 1214502, 4215, 4182, 16843009, 531997741, 857783146, 47226373, 1948036, 531997741]
Powyżej 1000 zaobserwować można kilka dodatkowych pętli, w tym dwie nietrywialne (jedna 3-elementowa i jedna 11-elementowa). Ale przyznam się szczerze, że pisanie tego artykułu zmęczyło mnie już na tyle, że odszukanie tych pętli (oraz, być może, poszukiwanie innych ciekawostek związanych z sumami potęg cyfr) pozostawię już Czytelnikowi.
Nuda, panie...
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.