Sumy i iloczyny, czyli o trwałościach

Dwa ciągi zaczynają się taką samą liczbą:

(1) 3367, 378, 168, 48, 32, 6

(2) 3367, 19, 10, 1

Pierwszy zwany jest iloczynowym, bo każdy następny wyraz stanowi iloczyn cyfr poprzedniego. W drugim każdy kolejny wyraz jest wynikiem dodawania cyfr poprzedniego, stąd nazwa – ciąg sumowy. Końcowa jednocyfrowa liczba w ciągu (1) to ostateczny iloczyn cyfr (OIC), w ciągu (2) – ostateczna suma cyfr (OSC).

Obliczanie OSC jest znane przynajmniej od wieków średnich. Ówcześni rachmistrze, chcąc sprawdzić, czy jakaś duża liczba dzieli się przez 9, tworzyli ciąg sumowy:

69 939 769 → 58 → 13 → 4

Jeśli OSC było równe 9, to 9 było dzielnikiem sprawdzanej liczby (cecha podzielności). Później z OSC korzystano także w innych celach; bywało na przykład testem „niekwadratowości”: jeżeli nie równa się 1, 4, 7 lub 9, to sprawdzana liczba na pewno kwadratem nie jest. W przykładzie OSC=4, czyli liczba zaczynająca ciąg może być kwadratem. Łatwo sprawdzić, korzystając z kalkulatora, że tak właśnie jest.

Znacznie krócej, bo od niespełna półwiecza, znane jest OIC; ściślej – znane jest w kontekście związanego z obydwoma powyższymi ciągami pojęcia trwałości liczby. Trwałość wyraża się liczbą o 1 mniejszą od liczby wyrazów w ciągu, kończącym się liczbą jednocyfrową, a więc równa jest liczbie kroków (odstępów) między wyrazami. Trwałość iloczynowa T_I liczby 3367 wynosi zatem 5, a trwałość sumowa T_S=3.

Pojęcie trwałości i odpowiadające jej ciągi pojawiały już w tej rubryce, ale temat warto rozwinąć i uzupełnić. Na początek przypomnę, że najprawdopodobniej T_I żadnej liczby nie jest większe niż 11, czyli żaden ciąg iloczynowy nie składa się z więcej niż 12 wyrazów. To hipoteza poparta komputerowym sprawdzeniem T_I wszystkich liczb w zakresie do gigantów złożonych z kilkudziesięciu tysięcy cyfr. Najmniejsze liczby o trwałościach 1, 2, … , 11 tworzą ciąg: 10, 25, 39, 77, 679, 6788, 68 889, 2 677 889, 26 888 999, 3 778 888 999, 277 777 788 888 899. Ostatnia liczba zaczyna liczący 12 wyrazów ciąg iloczynowy: 277 777 788 888 899 → 4 996 238 671 872 → 438 939 648 → 4 478 976 → 338 688 → 27 648 → 2688 → 768 → 336 → 54 → 20 → 0.

Nietrudno wskazać elementy ograniczające trwałość, a więc i długość ciągów iloczynowych, które są malejące niejako z natury, ponieważ każda liczba jest większa od iloczynu swoich cyfr. Jeśli bowiem liczba c-cyfrowa zaczyna się cyfrą a, to jest nie mniejsza niż a×10^c-1, a iloczyn jej cyfr nie przekracza a×9^c-1, zaś 10^c-1>9^c-1. Wyrażenie (10/9)^c-1 określa, ile co najmniej razy większa może być liczba od iloczynu jej cyfr. Gdy wyrażenie to przekracza 10n, to znaczy, że iloczyn cyfr danej liczby jest od niej krótszy o co najmniej n cyfr. Z obliczeń wynika, że iloczyn cyfr każdej liczby złożonej z co najmniej 22k cyfr (k=1, 2, 3 …) jest o co najmniej k cyfr krótszy od tej liczby. Finał ciągu iloczynowego będzie więc zawsze jednocyfrowy, ale głównym hamulcem jest zero, które pojawiwszy się w iloczynie natychmiast „wyzerowuje” ciąg. Obecności zera nie sposób przewidzieć poza jednym przypadkiem – zerem na końcu liczby, generowanym przez iloczynowe współdziałanie liczby parzystej i piątki – zatem para ta wyznacza dwa kroki do końca ciągu.

Każda liczba w ciągu iloczynowym, oprócz pierwszej, jest iloczynem liczb jednocyfrowych; inaczej mówiąc, jest tzw. liczbą 7-gładką, czyli w jej rozkładzie na czynniki pierwsze nie ma liczb większych niż 7. Tylko takie liczby – z co najmniej dwucyfrowym iloczynem cyfr oraz niezawierające zera, a także równocześnie liczby parzystej i piątki – stwarzają szansę (ale nie dają pewności) na przedłużenie ciągu chociaż o trzy kroki. Szkopuł w tym, że takich liczb jest bardzo mało, np. mniejszych od tysiąca zaledwie 52, a ich względny udział w większych zakresach szybko maleje (89 w zakresie do dziesięciu tysięcy), a to pośrednio wpływa na długość, a właściwie na krótkość ciągu.

Cechą nietypową ciągów liczbowych w ogólności, ale właściwą ciągom iloczynowym, jest to, że zaczynają się one nie tyle od liczby, ile od zbioru cyfr, które tworzą liczbę po ustawieniu ich w określonej kolejności, czyli wartość tej liczby nie jest istotna. Ponadto te liczby jednocyfrowe, które są liczbami złożonymi, można rozłożyć na czynniki pierwsze, co także nie zmienia trwałości. W efekcie od drugiego wyrazu ciąg może być identyczny dla wielu różnych początkowych liczb. Na przykład, drugi wyraz równy 72 może być poprzedzony jednym z 58 pierwszych, poczynając od najmniejszego 89, a kończąc na największym 33222 (wszystkie permutacje zbiorów: {8,9}, {2,4,9}, {2,6,6}, {3,3,8}, {3,4,6}, {2,2,2,9}, {2,2,3,6}, {2,3,3,4}, {2,2,2,3,3}). Tylko 58 możliwości jest oczywiście wówczas, gdy w zbiorach nie uwzględniamy jedynek, które nie wpływają na T_I.

Jeśli pominąć liczby z jedynkami na początku ciągu, to można podać nie tylko najmniejszą, ale i największą liczbę dla każdej trwałości T_I>2. Na przykład największą liczbą z T_I=11 jest liczba 29-cyfrowa spokrewniona z podaną wyżej najmniejszą (łatwo zauważyć, na czym polega pokrewieństwo):

77 777 733 332 222 222 222 222 222 222

Największa bezjedynkowa liczba o T_I≥3 liczy 280 cyfr, a jej skrócony zapis to 7₂₈3₂₂₇2₂₅ (28 siódemek, potem 227 trójek i na końcu 25 dwójek). Iloczyn cyfr każdej większej liczby bez zer i jedynek zawiera zero, zatem T_I każdej większej liczby równa jest 1 lub 2.

Wracając do trwałości sumowej: T_S w przeciwieństwie do T_I nie jest ograniczona, ale rośnie bardzo wolno, czyli dla stosunkowo małych T_S liczby zaczynające ciągi sumowe osiągają astronomiczne wartości. 19 jest najmniejszą liczbą, której T_S=2, zatem T_S=3 pojawia się przy liczbie, której suma cyfr równa jest 19, czyli przy 199. Z kolei najmniejsza liczba z sumą cyfr 199 to jedynka przewodząca 22 dziewiątkom. Podążając tym tropem, dotrzemy do każdej najmniejszej liczby o danej trwałości sumowej, jednak przykłady wypada zakończyć na T_S=5, która debiutuje przy liczbie złożonej z poprzedzonych jedynką 2 222 222 222 222 222 222 222 dziewiątek.

Zero w liczbie nie wpływa na trwałość sumową, natomiast jedynka ma znaczenie. W przypadku trwałości iloczynowej jest odwrotnie: jedynka nic nie zmienia, a zero to główny hamulec. A gdyby pozbyć się tego hamulca, czyli pomijać zero w mnożeniach (a×b×0≡a×b, a×0≡a)? Taki niezbyt odkrywczy, ale analitycznie ciekawy wariant trwałości zaproponował koryfeusz XX-wiecznej matematyki Paul Erdős. Na ogół trwałość iloczynowa Erdősa (T_IE) dla konkretnych liczb nie przewyższa trwałości T_I tak bardzo, jak można by się spodziewać, choć zdarza się ponad dwukrotnie większa. Na przykład dla liczby 77 889 999 999 zero pojawia się w drugim wyrazie ciągu, czyli T_I=2, natomiast T_IE=7:

77 889 999 999 → 14 999 390 784 → 17 635 968 → 272 160 → 168 → 48 → 32 → 6

Ciąg najmniejszych liczb o trwałości 1≤T_IE≤10 jest taki sam, jak dla trwałości T_I. Dopiero najmniejsza liczba z T_IE=11 jest nieco mniejsza niż w przypadku T_I=11, choć także 15-cyfrowa: 267 777 777 889 999, a zaczynający się nią ciąg iloczynowy Erdősa wygląda tak: 267 777 777 889 999 → 4 149 707 998 464 → 438 939 648 → 4 478 976 → 338 688 → 27 648 → 2688 → 768 → 336 → 54 → 20 → 2.

Jak widać, od trzeciego wyrazu do przedostatniego ciąg ten jest taki sam, jak podany wyżej ciąg odpowiadający trwałości T_I=11, czyli iloczyny cyfr drugich wyrazów obu ciągów (pomijając zero w drugim ciągu) są jednakowe.

Trwałość T_IE nie kończy się oczywiście na 11, ale Erdős sugerował, że jednak jest ograniczona i udowodnienie tego oraz znalezienie granicznej wartości uważał za znacznie trudniejsze wyzwanie niż dowód, że T_I nie przekracza 11. Tymczasem obie hipotezy do dziś nie zmieniły się w twierdzenia. Ponadto wiele wskazuje na to, że Erdős się mylił, bowiem wraz ze wzrostem mocy obliczeniowej komputerów odkrywane są liczby o coraz większej trwałości T_IE. Potwierdza to choćby sprawdzanie kolejnych potęg dwójki, zaczynając od 2⁴=16, której T_IE=1, a kończąc, na razie, na 2¹⁹³⁷⁰ (liczba 5831-cyfrowa) z T_IE=18. W sierpniu bieżącego roku dwaj francuscy informatycy, testując liczby złożone z jednakowych cyfr, ustanowili aktualny rekord – odkryli liczbę o T_IE=26 złożoną z 8 915 882 ósemek. Niezależnie od tego trwają poszukiwania najmniejszych liczb o konkretnych, dużych T_IE. Dotychczas największą T_IE, co do której mamy pewność, jakiej minimalnej liczby dotyczy, jest 18, a tą najmniejszą liczbą, złożoną z 2345 cyfr, jest 3₁7₁₄₀8₂₅₈9₁₉₄₆.

Trwałość jest cechą liczb przynajmniej dwucyfrowych. Jeśli przyrównać ją do trwałości produktów, to można stwierdzić, że liczby „zużywają się” w wyniku działań na tworzących je cyfrach, czyli w procesie, którego przejawem jest ciąg malejący – aż stają się „bezużyteczne” jako jednocyfrowe. Miarą trwałości jest oczywiście długość ciągu.

Miłośnicy rekreacyjnej teorii liczb wymyślili jeszcze jeden nieco przewrotny rodzaj trwałości, w którym liczby tracą „użyteczność” jako wielocyfrowe, a ciągi są rosnące. To tzw. trwałość wzrostowa T_W, łącząca elementy trwałości T_I i T_S. W odpowiadającym jej ciągu T_W każdy kolejny wyraz jest sumą wyrazu poprzedniego i iloczynu jego cyfr. Wartość T_W określa liczba odstępów między wyrazami w ciągu rosnącym, a więc do pierwszego wyrazu z zerem, bo wówczas ciąg zmienia się w stały. Na przykład z ciągu rozpoczynającego się od 11 wynika, że T_W tej liczby równa się 8:

11 → 12 → 14 → 18 → 26 → 38 → 62 → 74 → 102, 102, 102, …

Ciekawe, że w przypadku T_W liczb dwucyfrowych liczba 102 ogranicza trwałość najczęściej. Drzewo na 102, czyli graf obejmujący wszystkie ciągi wiodące do tej liczby, ma nad trzycyfrowym korzeniem aż 19 dwucyfrowych wierzchołków. Na drugim miejscu jest znacznie mniej wybujały (11 wierzchołków) krzew z korzeniem 110 (rys. 1).

Czy ciąg rosnący T_W zawsze zostanie zahamowany wyrazem zawierającym zero? Wprawdzie hamowanie jest słabsze niż w przypadku T_I, ale nieuchronne. Gdy w ciągu pojawia się pierwszy wyraz (c+1)-cyfrowy (p), to do poprzedniego wyrazu, mniejszego od 10^c, dodawany jest iloczyn jego cyfr nie większy niż 9^c. Dla małych c druga cyfra wyrazu p może być różna, np. równa 4 (79 → 142) lub 1 (857 → 1137). Gdy jednak c jest dostatecznie duże, to iloczyn cyfr wyrazu poprzedzającego p nie spowoduje, że druga cyfra wyrazu p przekroczy zero. Konkretnie: zero na drugiej pozycji jest nieuniknione dla c>21.

Czy wyraz z zerem, kończący trwałość wzrostową, może wystąpić dowolnie daleko w ciągu, czy też jest granica jego zasięgu; inaczej mówiąc, czy istnieje maksymalna wartość T_W? Tego nie wiadomo. Dotychczas poszukiwania najmniejszych liczb z konkretnymi wartościami T_W zakończyły się na 14-cyfrowym okazie 35 632 297 938 395 o T_W=40. W 40 wyrazach ciągu zaczynającego się tą liczbą nie ma zera. Pojawia się dopiero w 41 wyrazie – 35 731 971 677 045 – który kończy ciąg rosnący, a zaczyna stały.

A gdyby do trwałości wzrostowej zastosować pomysł Erdősa, czyli pomijać zero w mnożeniach? W takim przypadku trudno byłoby mówić o konkretnej trwałości, bo ciąg zaczynający się od dowolnej liczby będzie wówczas nieskończony, czyli każda liczba, a ściślej jej „przeobrażenia” będą wiecznotrwałe. Co ciekawe, główny ciąg, zaczynający się od 10 (10 → 11 → 12 → 14 → 18 → 26 → 38 → 62 → 74 → 102 → 104, …) zbiera wszystkie pozostałe ciągi niczym rzeka dopływy, więc ogół „cieków” przypomina gigantyczne, bezkresne dorzecze, którego zaczątek przedstawiony jest jako drzewo na rys. 2.

Zadania

1. Jaka jest najmniejsza liczba, której trwałość iloczynowa Erdősa (T_IE) jest większa od jej zwykłej trwałości iloczynowej T_I ?

2. W ciągu, który od pewnego wyrazu jest stały, każdy kolejny wyraz stanowi iloczyn poprzedniego wyrazu i sumy jego cyfr. Jaką najmniejszą liczbą inną niż 10ⁿ zaczyna się ten ciąg?

3. Ciąg zaczyna się jedynką, a każdy kolejny wyraz jest sumą wyrazu poprzedniego i tworzących go cyfr. W ciągu tym znajduje się jedna z trzech następujących liczb: 105 288, 3 105 288, 31 054 288. Która?

4. Dwa ciągi – sumowy i iloczynowy – zaczynają się taką samą liczbą złożoną z trzech różnych cyfr. Trzeci wyraz ciągu sumowego jest o 1 większy niż czwarty wyraz ciągu iloczynowego. Jaką liczbą jest drugi wyraz ciągu iloczynowego?

5. W ciągu zaczynającym się liczbą 145≤x≤149 każdy następny wyraz jest sumą lub różnicą poprzedniego wyrazu i iloczynu jego cyfr. Jaką konkretną liczbą jest x, skoro x powtarza się w ciągu jako jeden z kolejnych wyrazów? Jeśli możliwe jest więcej niż jedno rozwiązanie, należy podać wszystkie.

Rozwiązania prosimy nadsyłać do 31 grudnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 12/20. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Davida Attenborough Podróże na drugi kraniec świata. Dalsze przygody młodego przyrodnika ufundowaną przez wydawnictwo Prószyński Media. 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 październikowego

1. Całkowicie różnych podziałów kwadratu 4×4 na dwa 8-kratkowe sektory jest 13 (rysunek), a jeśli uwzględnić obroty i odbicia lustrzane – mnożąc liczby podziałów w pierwszym, drugim i trzecim wierszu na rys. 3 odpowiednio przez 2, 4 i 8 – to liczba ta wzrośnie do 70.

2. W podzielonym na 4-kratkowe części (tetromina) diagramie 8×8 trzy części mają kształt litery L (pełne rozwiązanie na rys. 4).

3. W podzielonym na 8-kratkowe części diagramie 8×8 dwie części są ośmiokątami (pełne rozwiązanie na rys. 5).

4. Trzy „strzały”, umożliwiające odtworzenie podziału diagramu w grze LAP przedstawionego na rys. 6, są następujące: ab-45 (odp. II-4); fg-12 (odp. II-2, III-1, IV-1); ef-78 (odp. I-1, II-3).

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Lepsza połowa. O genetycznej wyższości kobiet Sharona Moalema, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Paweł Chmiel, Monika Fiołna, Maciej Golimowski, Małgorzata Grela, Joanna Kotwica.