Przeskocz do treści

Delta mi!

Loading

Polowanie na ciągi

Bartłomiej Pawlik

o artykule ...

  • Publikacja w Delcie: listopad 2016
  • Publikacja elektroniczna: 1 listopada 2016
  • Autor: Bartłomiej Pawlik
    Afiliacja: doktorant, Zakład Algebry, Wydział Matematyki Stosowanej, Politechnika Śląska
  • Wersja do druku [application/pdf]: (199 KB)

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...

obrazek

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:

obrazek

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

obrazek

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).