Potęgowanie i sumowanie
czyli iteracja według Steinhausa MAREK PENSZKO
ODODAWANIU CYFR TWORZąCYCH LICZBY, a ściślej – o związanych z takim działaniem kilku ciekawych zagadnieniach – pisałem w tej rubryce przed niespełna rokiem (06/2023). Zapewne większości temat ten kojarzy się z cechą podzielności przez 3 lub 9, jako jedyną szerzej znaną zależnością między sumą cyfr liczby a jej konkretną własnością. Dodawanie dominowało we wspomnianych zagadnieniach, ale nie było jedynym działaniem. Zwykle wiązało się z mnożeniem lub dzieleniem, jak na przykład w przypadku szukania takich wielokrotności bn liczb n, których suma cyfr równa jest sumie cyfr n, czyli S(bn)=S(n).
Wbrew pozorom nie zawsze jest to proste zadanie. Na przykład aby otrzymać najmniejszą wielokrotność n=41 z S(n)=5, trzeba pomnożyć n przez b=7561, bo dopiero wtedy S(bn)=5 (bn=41×7561=310 001). Ponadto można dowieść, że dla n=12 z S(n)=3 oraz n=25 z S(n)=7 szukanie jest bezcelowe, bo dla tych wartości n odpowiednich wielokrotności S(bn) po prostu nie ma.
Ten artykuł dotyczy pokrewnego tematu: sumowania potęg cyfr tworzących liczby. W tym kontekście odpowiednikiem wspomnianego zagadnienia jest szukanie takich liczb n, których suma cyfr równa jest sumie cyfr ich k-tych potęg, czyli S(n)=S(nk). Łatwo zauważyć, że do spełniających tę równość liczb należą m.in. te, które można nazwać trywialnymi.
Zaliczamy do nich:
– liczby, dla których podany wzór jest prawdziwy przy każdej wartości k – są nimi wszystkie potęgi 10, zaczynając od 100=1;
– liczby spełniające równość S(n)=S(nk) z dopisaną dowolną liczbą zer.
Wśród pozostałych, nietrywialnych liczb n (bez zera na końcu) tym mniej pasuje do wzoru i tym trudniej je znaleźć, im większe jest k. Zwłaszcza że nie jest znana inna metoda poszukiwań niż siłowa.
Dla k=2 nietrywialne liczby n tworzą ciąg: 9, 18, 19, 45, 46, 55, 99, 145, 189, 198, 199, 289, 351, 361, 369, 379, 388, 451, 459, 468, 495, 496, 558, 559, 568, 585, 595, 639, 729, 739, 775, 838, 855, 954, 955, 999, 1098, … . Każdą można określić wzorem 9x lub 9x+1 (dla pewnych wartości x) albo inaczej – jako równą 0 lub 1 mod 9. Z obliczeń wynika, że w zakresie do miliona ciąg ten liczy blisko siedmiu tysięcy wyrazów, a teoretycy liczb udowodnili, że jest on nieskończony. Osobliwość stanowi występujący w nim kwadrat 361, co owocuje dwustopniową równością: S(n)=S(n2)=S[(n2)2], czyli S(19)=S(361)=S(130 321)=10.
Dla k=3 nietrywialne n występują wśród liczb naturalnych znacznie rzadziej. Tworzą ciąg: 8, 171, 378, 468, 487, 577, 585, 586, 684, 4877, … . Do miliona jest ich tylko 44, a każdy równy 0, 1 lub 8 mod 9.
Dla k=4 znamy tylko pięć nietrywialnych n: 7, 19, 67, 57 999 659 949, 84 936 699 999, … , ale udowodniono, że to początkowy fragment nieskończonego ciągu. Nieskończone są także analogiczne ciągi dla większych k,
tylko że nie zostały one jeszcze… zaczęte. Po prostu nie ma komputerów chętnych do szukania gigantycznych pierwszych wyrazów, nawet dla k=5.
W wydanej w 1958 roku książce Sto zadań Hugo Steinhaus zamieścił zadanie poprzedzone opisem ciekawej iteracji (jako pierwszy zwrócił na nią uwagę kilkanaście lat wcześniej amerykański matematyk Arthur Porges): dodajemy do siebie kwadraty cyfr tworzących dowolną liczbę, a z otrzymaną sumą i z każdą następną postępujemy tak samo. Należy dowieść, że możliwe są tylko dwie pętle kończące taką wieloetapową operację – pewien 8-liczbowy cykl albo powtarzająca się jedynka, czyli „cykl” 1-liczbowy.
Istota dowodu sprowadza się do ograniczenia zbioru liczb, które należy poddać wskazanej „obróbce”, aby ustalić obecność tylko dwóch unikalnych zapętleń. Łatwo wykazać, że:
a) suma kwadratów cyfr każdej liczby 4-cyfrowej jest 3-cyfrowa, równa co najwyżej 4×92=324;
b) suma kwadratów cyfr każdej liczby 3-cyfrowej jest od tej liczby mniejsza (a2+b2+c2<100a+10b+c).
W cyklu liczbowym występuje wartość minimalna, na której kończy się spadek, a zaczyna wzrost wartości liczb lub – jeśli cykl jest 1-liczbowy – następuje „stabilizacja”. W tym przypadku, ze względu na warunek (b), tym minimum nie może być liczba 3-cyfrowa. Wystarczy więc sprawdzić liczby 2-cyfrowe, aby trafić na minimum, a tym samym na szukany cykl. 1-cyfrowe liczby można pominąć, bo gdy są większe niż 1 zawsze rosną do 2-cyfrowych. Ponadto można ograniczyć się do określonych par cyfr, czyli na przykład po sprawdzeniu 28 testowanie 82 nie jest już konieczne, bo efekt końcowy będzie taki sam – w tym konkretnym przypadku pojawi się jedynka: 28 (82) → 68 → 100 → 1. Wszystkie liczby docierające do jedynki zwane są w teorii liczb „szczęśliwymi”. W zakresie do 100 jest ich 20 (1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, …). Dwójka jest zatem pierwszą, która wpada w dłuższy cykl: 2 → [4 → 16 → 37 → 58 → 89 → 145 → 42 → 20] → 4 → 16, … . Może się wydawać, że im większa liczba startowa, tym większa szansa na to, że droga do jedynki lub do cyklu będzie dłuższa. Tymczasem zależność ta jest bardziej złożona. Dotarcie do 1 od 7 wymaga pięciu iteracji: 7 → 49 → 97 → 130 → 10 → 1, … ; aby kroków było sześć, trzeba zacząć przynajmniej od 356 (356 → 70 → 49 → … → 10 → 1, ...), a siedem etapów pojawia się dopiero przy 78 999 (78 999 → 356 → … → 10 → 1, ...). Natomiast podanie tu (bez zmiany stopnia pisma) najmniejszej liczby, od której należałoby zacząć, aby dotrzeć do jedynki w ośmiu krokach, zajęłoby prawie ćwierć strony (blisko tysiąc cyfr). Podobnie wygląda zależność, gdy celem jest 8-liczbowy cykl, bo wśród liczb, które do tego prowadzą, czyli „nieszczęśliwych”, jest jeszcze względnie mała (5-cyfrowa) ta, od której do cyklu dociera się w 12 krokach: 15 999 → 269 → 121 → 6 → 36 → 45 → 41 → 17 → 50 → 25 → 29 → 85 i 89 jako początek cyklu. Natomiast tę, która zaczyna 13-etapową drogę, wypada już przedstawić tak: 577 przewodzące 196 dziewiątkom. Łatwo sprawdzić, że liczba ta daje w pierwszym kroku sumę kwadratów cyfr oddaloną od celu o 12 kroków, czyli 15 999.
Czy suma kwadratów cyfr jakiejś liczby większej od 1 może być równa tej liczbie? Odpowiedź musi być przecząca, bo rozwiązaniem zadania Steinhausa nie jest liczba 2-cyfrowa o takiej własności, jak 1, czyli stabilna w procesie iteracji. A czy taka równość jest możliwa, gdy sumowane będą sześciany cyfr, a więc czy równanie a3+b3=ab lub a3+b3+c3=abc lub a3+b3+c3+d3=abcd ma rozwiązanie (podkreślenie
oznacza, że chodzi o 2-, 3- i 4-cyfrową liczbę, a nie o mnożenie; cyfry a, b, c, d nie muszą być różne)?
Rozwiązania tego problemu pojawiły się po raz pierwszy w roku 1937 w poświęconym matematyce popularnej belgijskim magazynie „Sphinx”. Dziś ich znalezienie z pomocą komputera jest bardzo proste, ale przed blisko wiekiem stanowiło nie lada wyzwanie dla cierpliwych. Rozwiązania są cztery, wszystkie 3-cyfrowe: 153, 370, 371 i 407 (np. 153=13+53+33). Do 2- i 4-cyfrowych jest blisko, ale są o 3 za duże – 12, 30, 31 lub o 3 za małe – 32, 1799; przykłady: 31=33+13+3, 1799=13+73+93+93–3.
Powiązanie powyższych czterech rozwiązań z zadaniem Steinhausa, które po przetłumaczeniu „Stu zadań” na kilka języków stało się znane na świecie, zainspirowało teoretyków liczb do uogólnienia problemu: każda cyfra danej liczby podnoszona jest do k-tej potęgi; wyniki są sumowane, a ta suma i każda kolejna podlega takiemu samemu zabiegowi. Szukamy wszystkich możliwości „zapętlenia” serii takich iteracji dla danego k≥ 3. Poszukiwania są kuszące, bo wyniki trudno przewidzieć. Wiadomo tylko, że zapętlenia muszą nastąpić, bo dla każdego k zbiór sum potęg cyfr jest ograniczony.
Na przykład dla k=3 sięga tylko liczb 4-cyfrowych, a konkretną granicę stanowi 4×93=2916. Praktycznie jednak ograniczeniem przy poszukiwaniach jest największa liczba, która ma zadatki na bycie minimum w cyklu, czyli z sumą sześcianów większą od niej samej – tą liczbą jest 1999. I – co ciekawe – właśnie ta liczba prowadzi do jednego z cykli: 1999 → 2188 → 1033 → [55 → 250 → 133] → 55, … . Poza tym 3-liczbowym cyklem – oraz podanymi wyżej czterema „stabilizatorami” i niezawodną jedynką – przy k=3 pojawiają się jeszcze trzy cykle: jeden 3-liczbowy [160 → 217 → 352] oraz dwa 2-liczbowe [136 → 244] i [919 → 1459].
Dla k=4 jest jeden cykl 7-liczbowy – [1138 → 4179 → 9219 →
13139 → 6725 → 4338 → 4514], jeden 2-liczbowy – [2178 → 6514] i pięć cykli stabilizatorów: 1, 1634, 2178, 8208, 9474.
Dla k=5 stabilizatorów jest siedem: 1, 4150, 4151, 54 748, 92 727, 93 084, 194 979, a dłuższych cykli dziewięć: dwa 2-liczbowe – [58 618 → 76 438] i [89 883 → 157 596]; dwa 10-liczbowe – [8294 → 92 873 → … → 26 663 → 23 603] i [9044 → 61 097 → … → 133 682 → 41 063] oraz po jednym: 4-liczbowy – [10 933 → 59 536 → 73 318 → 5062], 6-liczbowy – [8299 → 150 898 → … → 68 335 → 44 155], 17-liczbowy – [24 584 → 37 973 → … → 26 093 → 67 100], 22-liczbowy – [9045 → 63 198 → … → 79 467 → 101 463] i wreszcie 28-liczbowy gigant, choć zaczynający się najmniejszą liczbą – [244 → 2080 → … → 213 040 → 1300].
Znane są jeszcze rozwiązania zadania Steinhausa, czyli wszystkie końcowe cykle, dla potęg k=6 i 7. Sąsiednia tabela obejmuje statystykę rozwiązań dla 2≤k≤7 – liczbę wszystkich cykli L(c), liczbę cykli jednoliczbowych L(cs), czyli stabilizatorów oraz c(max), czyli najdłuższy cykl dla danego k (w nawiasie najmniejsza liczba w tym cyklu).
Trudno doszukać się w tych wartościach jakichś prawidłowości. Układ liczb w trzech kolumnach wydaje się losowy. Można tylko zauważyć, że liczba cykli dla nieparzystych k jest większa niż dla parzystych. Na uwagę zasługują też stabilizatory, a ściślej odpowiadające im osobliwe zapisy dodawań potęg kolejnych cyfr, dające sumy złożone z podstaw kolejnych potęg. Oto siedem z wykładnikami potęg od 3 do 9 i największą sumą dla każdej potęgi:
43+03+73=407 94+44+74+44=9474 15+95+45+95+75+95=194 979 56+46+86+86+36+46=548 834 17+47+47+57+97+97+27+97=14 459 929 88+88+58+98+38+48+78+78=88 593 477 99+19+29+99+89+59+19+59+39=912 985 153
ZADANIA
1. Suma sześcianów cyfr 3-cyfrowej liczby pierwszej P3 równa jest 4-cyfrowej liczbie pierwszej P4. Jaką liczbą jest P3, jeśli pierwsza cyfra obu liczb jest taka sama?
2. Suma sześcianów cyfr liczby A równa jest kwadratowi sumy cyfr liczby A, a także sumie cyfr kwadratu liczby A. Jaką liczbą jest A, jeśli nie ma w niej zera ani jedynki?
3. Każdą liczbę w ciągu liczb naturalnych zmieniono w taki sam sposób, wykonując określone działania na jej cyfrach. Powstał ciąg w którym poprzednia liczba 12 została zmieniona w 5, liczba 345 – w 144, a liczba 6789 – w 7128. Jaką liczbą jest w tym ciągu ta, która powstała po zmianie liczby 6394?
Rozwiązania prosimy nadsyłać do 30 kwietnia 2024 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 04/24. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Czarne dziury. Klucz do zrozumienia
Wszechświata Briana Coxa, Jeffa Forshawa ufundowaną przez wydawnictwo Sensus.
Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:
Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji konkursu.
Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl.
ROZWIĄZANIA ZADAŃ Z NUMERU LUTOWEGO
1. Liczbą-anagramem 0189, która oprócz 1809 ma dwa generatory addytywne, jest 8019 – są to liczby 8010 i 7992.
2. Liczbami podzielnymi przez swoje „wspaki” są oprócz 9801 i 8712 także 5610 (165×34), 5940 (495×12) i 8910 (198×45).
3. Liczbą-anagramem 0189, która może być zapisana na najwięcej sposobów jako suma kolejnych liczb, jest 8190. Sposobów jest tyle, co nieparzystych dzielników, czyli 23.
4. Największa „kwadratowa” obniżka ceny wynosiła 6084 zł (782) – z 7981 zł do ceny wspak – 1897.
5. Największy zakres dzielników – od 2 do 32 – obsługują liczby tworzone z cyfr 0, 1, 4, 5 lub 0, 4, 5, 6 – przy założeniu, że każda liczba musi składać się z różnych cyfr.
Za poprawne rozwiązanie przynajmniej trzech zadań książkę popularnonaukową otrzymują: Krzysztof Foszcz i Renata Nowak (oboje z Krakowa), Damian Kwiatkowski z Wrocławia, Wojciech Koziński i Aleksander Urban (obaj z Warszawy).