Polowanie na ciągi

W 1964 roku amerykańsko-brytyjski matematyk Neil Sloane zaczął kolekcjonować znane ciągi liczb całkowitych. Niewinne hobby, motywowane zbadaniem własności kilku ciągów, które pojawiły się podczas pracy nad jego rozprawą doktorską, szybko przerodziło się w duże przedsięwzięcie. W efekcie zostały opublikowane dwie książki A Handbook of Integer Sequences (wydana w roku 1973, zawierająca 2372 ciągi) oraz The Encyclopedia of Integer Sequences (z 1995 roku, 5847 ciągi). W 1996 roku, gdy liczba zgromadzonych ciągów przekroczyła 10 000, dalsze ich przechowywanie w postaci książkowej stało się bardzo niepraktyczne...

Sloane postanowił stworzyć internetową bazę ciągów, dziś figurującą pod nazwą OEIS (The On-Line Encyclopedia of Integer Sequences). Baza zawiera obecnie około 270 000 ciągów i, aby uświadomić sobie jej wartość jako przydatnego narzędzia w pracy badawczej, wystarczy wspomnieć, że już ponad 4500 artykułów naukowych zawiera informację: Otrzymanie tego wyniku nie byłoby możliwe bez pomocy OEIS.

Znalezienie nietrywialnego ciągu liczb całkowitych, który nie figuruje na wspomnianej liście, nie jest łatwym zadaniem. W niniejszym tekście zaprezentuję, w jaki sposób udało się upolować jeden okaz. Polowanie zacznijmy od próby znalezienia odpowiedzi na właściwie błahe pytanie:

Ile jest liczb naturalnych $k,$ takich, że liczba $|k!$ ma dokładnie $k$ cyfr?

Niech $|λ N N$ będzie funkcją określającą liczbę cyfr danej liczby (przykładowo $|λ(2016) = 4$ ). Powyższe pytanie możemy sformułować teraz w następujący sposób: ile rozwiązań ma równanie $|k =λ (k!)?$ Tabela obok przedstawia wartości funkcji $λ (k!)$ dla małych $|k.$

Jak widać, wśród liczb jednocyfrowych jest tylko jedno rozwiązanie (liczba $|1!$ ma dokładnie jedną cyfrę). Bardzo szybki wzrost wartości funkcji $|k!$ sprawia, że poszukiwanie większych rozwiązań "na piechotę" jest niezwykle nieporęczne. Z drugiej strony szybki wzrost sugeruje, że liczba rozwiązań jest skończona. Zauważmy, że liczba $100!$ ma o dwie cyfry więcej niż $99!.$ Ujmując to nieco ogólniej, jeżeli $100 ⩽ k < 1000,$ to

λ((k− 1)!)+ 2⩽ λ(k!) ⩽ λ((k −1)!)+ 3.

Powyższa nierówność wynika z faktu, że gdy pomnożymy dowolną liczbę przez liczbę trzycyfrową, liczba jej cyfr zwiększy się o 2 lub 3. Najmniejsze $|k,$ takie, że $λ(k!) =λ ((k− 1)!)+ 3,$ to $k = 104.$

Z powyższych nierówności wynika oszacowanie:

λ (200!)⩾ λ(100!)+ 2 ⋅100 = λ(100!)+ 200 > 200,

czyli liczba $|200!$ ma więcej niż 200 cyfr. Co więcej, dla każdego $|k$ większego od 200 liczba $k!$ ma więcej niż $|k$ cyfr. Zatem jeżeli istnieją różne od 1 rozwiązania równania $k = λ(k!),$ to są one na pewno mniejsze od 200.

Problem znalezienia wszystkich rozwiązań sprowadziliśmy do zbadania liczb z zakresu od 10 do 199. Jednak przeprowadzenie bezpośrednich obliczeń wciąż byłoby całkiem czasochłonne (ze względu na bardzo duże wartości liczby $k!$ nawet dla niewielkich $k$ ). Znajdźmy sposób!

Niech $|N! = {0!,1!,2!,3!,...}$ będzie zbiorem silni liczb naturalnych. Funkcja $|λ$ jest niemalejąca na zbiorze $N!$ (podobnie jak na zbiorze $N$ ), a po usunięciu z tego zbioru pierwszych sześciu elementów jest na nim rosnąca. Szukanie rozwiązań równania $k = λ(k!)$ dla $k ∈{10,11,...,199}$ można efektywnie przeprowadzić metodą bisekcji (tj. sprawdzić, czy rozwiązaniem jest element leżący mniej więcej w środku tego zbioru, a jeśli nie, to biorąc pod uwagę wartość funkcji $λ$ dla tego elementu, ograniczyć przeszukiwany zbiór do liczb mniejszych lub większych od tego sprawdzonego elementu).

Przedstawmy kilka początkowych kroków zastosowania tego algorytmu. $|λ(100!) = 158.$ Liczba $100!$ ma 158 cyfr w zapisie dziesiętnym, czyli wszystkie potencjalne rozwiązania będą znajdowały się w zbiorze $|{10,11,...,99}.$ $|λ(50!) = 65,$ więc wszystkie potencjalne rozwiązania będą znajdowały się w zbiorze ${10,11,...,49}.$ Kontynuując to rozumowanie, dochodzimy do wniosku, że jedynymi liczbami naturalnymi $k,$ takimi, że liczba $k!$ ma dokładnie $k$ cyfr, są 1, 22, 23 i 24.

Czy to już wszystko? Czy odpowiedź na pytanie będące zalążkiem polowania jest kompletna? A co by było, gdybyśmy rozważyli liczby zapisane w innych systemach pozycyjnych?

Odpowiedź na pytanie, ile jest liczb naturalnych $k,$ takich, że $|k!$ ma dokładnie $k$ cyfr, zależy, oczywiście, od podstawy systemu pozycyjnego, w którym rozpatrujemy liczbę $k.$ Niech $λ n(k)$ oznacza liczbę cyfr liczby $|k$ w systemie pozycyjnym o podstawie $n$ oraz niech $|Λ(n)$ oznacza liczbę takich liczb naturalnych $k,$ że liczba $|k!$ ma dokładnie $k$ cyfr w zapisie w systemie pozycyjnym o podstawie $|n.$ Czyli $Λ(1) = 2$ oraz $|Λ(10) = 4$ (co udowodniliśmy wcześniej). $|Λ(n)$ jest liczbą rozwiązań równania

k = λ (k!), dla n⩾ 2. n

Przez $Λn$ oznaczmy ciąg wartości funkcji $Λ.$ Jest to ciąg opisujący liczbę liczb $k,$ takich, że liczba $k!$ ma dokładnie $k$ cyfr w zależności od podstawy rozpatrywanego systemu pozycyjnego. I to jest właśnie ten ciąg, który padł ofiarą naszego polowania! Teraz można pokusić się o zbadanie pewnych jego własności, co pozostawiamy jako zadanie dla Czytelnika Niezmęczonego.

Wartości ciągu $|Λn$ rosną bardzo powoli. Czy istnieje jakieś ograniczenie górne tego ciągu? Jeżeli tak, to jakie?
Dla jakich liczb naturalnych $k,$ liczba $k!$ nie ma $k$ cyfr w żadnym systemie pozycyjnym?
Tablica obok sugeruje, że wraz ze wzrostem liczby $n$ (czyli podstawy systemu pozycyjnego), wszystkie nietrywialne (różne od 1) rozwiązania równania $k =⌊logn(k!)⌋+ 1$
zbliżają się do liczby $e ⋅n.$ Utwierdzająca w tym przekonaniu może być tablica rozwiązań dla początkowych potęg liczby $10$ :

$| |-----|-----------------| n |---n-|Λ---|Rozwią zania--| | 1| 2 |1, 2 | |-----|----|------------| |---10-|-4--|1, 22, 23, 24| | 100 | 6 |1, 264- 268 | |-----|----|------------| |-1000-|-8--|1,-2707- 2713--| -10000---10---1,-27168-27176--$
Formalnie ten wniosek można zapisać w postaci $⌊logn⌊en-⌋!⌋-+1- ln im+∞ en = 1.$
Czytelniku Poszukujący, spróbuj to udowodnić (np. stosując wzór Stirlinga).