Jak dotąd jest dobrze

Dziwaczna i zachwycająca chemia audioaktywnego rozkładu. Jedną z popularniejszych rekreacyjnych sekwencji liczbowych jest ciąg look-and-say wprowadzony przez Johna Conwaya w 1986 roku: $$1,11,21,1211,111221,312211,13112221,\dots$$ Czytelnikowi, który widzi powyższy ciąg po raz pierwszy, sugeruję na chwilę zatrzymać lekturę i zastanowić się, jaka powinna być następna liczba.

Nazwa look-and-say idealnie oddaje istotę ciągu – każdy kolejny wyraz powstaje przez opisanie tego, co widzimy, patrząc na wyraz poprzedni. Przykładowo, patrząc na piąty wyraz ciągu (111221), widzimy trzy (3) jedynki (1), dwie (2) dwójki (2) i jedną (1) jedynkę (1), więc kolejny wyraz to 312211. Rzeczona autodeskrypcyjność stanowi największy urok ciągu Conwaya: wyznaczenie kolejnych wyrazów nie ma nic wspólnego z niedostępną dla niewtajemniczonych matematyką wyższą. Można się nawet pokusić o przypuszczenie, że spostrzegawczy laik ma większe szanse na odgadnięcie reguły rządzącej ciągiem niż doświadczony matematyk. Moda na ciąg Conwaya nie ominęła Delty, na łamach której w ostatnich latach pojawiły się warte uwagi teksty traktujące o look-and-say: w ${\mathrm{\Delta }}_{21}^{11}$ o najważniejszych własnościach pisze Wojciech Czerwiński, a w ${\mathrm{\Delta }}_{23}^1$ można znaleźć bardziej szczegółowy tekst Karola Gryszki.

Jak dotąd jest dobrze. Bohaterem niniejszego artykułu jest pewien mniej znany ciąg autodeskrypcyjny, który zadebiutował w OEIS (The On-Line Encyclopedia of Integer Sequences – bardzo przydatna baza ciągów) w 2005 roku jako wytwór Erica Angeliniego – belgijskiego pasjonata matematyki rekreacyjnej. Zanim przedstawimy sam ciąg, przyjmijmy następującą konwencję dekodowania liczb. Niech $N\ge 10.$ Liczba powstała przez ,,odcięcie” ostatniej cyfry liczby $N$ (czyli część całkowita liczby $N/10$) będzie oznaczać ilość, a ostatnia cyfra liczby $N$ (czyli reszta z dzielenia $N$ przez 10) będzie oznaczała samą siebie, czyli – nomen omen – cyfrę. Liczbę $N$ dekodujemy jako odpowiednią ilość tej cyfry.

Przykładowo 26 dekodujemy jako dwie cyfry ,,6”, a 8945 jako osiemset dziewięćdziesiąt cztery cyfry ,,5”.

Sekwencja true-so-far jest rosnącym ciągiem liczb całkowitych, którego pierwszym elementem jest liczba 10, a każdy kolejny to najmniejsza liczba, która po zdekodowaniu poprawnie opisuje liczbę wystąpień danej cyfry we wszystkich dotychczasowych elementach ciągu (łącznie z wprowadzonym). Zatem drugim elementem ciągu nie może być liczba 11 (11 dekodujemy jako jedna ,,jedynka”, podczas gdy ciąg $(10,11)$ zawiera trzy jedynki!), natomiast liczba 12 tak (ciąg $(10,12)$ faktycznie zawiera jedną cyfrę ,,2”). Sto początkowych elementów ciągu true-so-far to: $$\begin{array}{ccccccccccccc}10,& 12,& 13,& 14,& 15,& 16,& 17,& 18,& 19,& 20,& 23,& 24,& 25,\\ 26,& 27,& 28,& 29,& 30,& 34,& 35,& 36,& 37,& 38,& 39,& 40,& 45,\\ 46,& 47,& 48,& 49,& 50,& 56,& 57,& 58,& 59,& 60,& 67,& 68,& 69,\\ 70,& 78,& 79,& 80,& 89,& 90,& 102,& 103,& 104,& 105,& 106,& 107,& 108,\\ 109,& 112,& 113,& 114,& 115,& 116,& 117,& 118,& 119,& 123,& 124,& 125,& 126,\\ 127,& 128,& 129,& 134,& 135,& 136,& 137,& 138,& 139,& 145,& 146,& 147,& 148,\\ 149,& 156,& 157,& 158,& 159,& 167,& 168,& 169,& 178,& 179,& 180,& 189,& 190,\\ 192,& 193,& 194,& 195,& 196,& 197,& 203,& 204,& 205.\end{array}$$ Ostatnia z zapisanych powyżej liczb, 205, informuje, że w tabeli znajduje się dokładnie dwadzieścia cyfr ,,5”.

Czy rozpatrywany ciąg jest nieskończony? Odpowiedź uzyskamy, łącząc liczenie na palcach (komputerowych) z prostym rozumowaniem.

Jak się okazuje, po otrzymaniu dwa tysiące dwudziestego czwartego elementu ciągu true-so-far – 8945 – liczby wystąpień poszczególnych cyfr są następujące: $$\begin{array}{|cccccccccc|}\hline 0& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 624& 822& 834& 864& 874& 894& 779& 697& 697& 617\\ \hline\end{array}$$

Kolejny, dwa tysiące dwudziesty piąty element ciągu musi mieć zakodowaną liczność jednej z dziesięciu cyfr. Zauważmy, że nie może on odnosić się do cyfry ,,5”: liczba 8955 nie pasuje, gdyż zwiększa liczbę piątek o dwie, a nie o jedną; podobnym argumentem odrzucamy liczbę 8965 (oczywiście większych kandydatów nie ma sensu rozpatrywać).

Analogicznie można uzasadnić, że kolejny element nie może mieć na końcu cyfry 8. Pozostali kandydaci to: $$6250,8231,8352,8653,8754,7806,6987,6189\text{ i }6199,$$ jednak odrzucamy każdą z tych propozycji ze względu na założenie, że rozpatrywany ciąg ma być rosnący – każda z dziewięciu powyższych liczb jest mniejsza od 8945. Ostatecznie ciąg true-so-far ma dokładnie 2024 elementy.

Pod koniec powyższego uzasadnienia skończoności powołaliśmy się na monotoniczność rozpatrywanego ciągu. Jak się okazuje, true-so-far ma skończoną liczbę elementów również w wariancie, w którym nie zakładamy, że jest rosnący. Jednak liczba elementów tej wersji ciągu przez długi czas nie da nam dobrego pretekstu do przedstawienia go na łamach Delty – zgodnie z informacją zamieszczoną w bazie OEIS wynosi ona $5191475.$