Dzielniki – kolejno odlicz! O sekretach dyskretnej funkcji tau

W Urzędzie Spraw Powszednich jest 99 pokoi. Dyrektor USP twierdzi, że drzwi do wszystkich – ponumerowane od 1 do 99 – zawsze stoją przed petentami otworem. Rzeczywistość jest jednak inna, bowiem każdego dnia rano urzędnicy dokonują pewnej manipulacji, która mocno ogranicza zestaw otwartych drzwi. Manipulacja ma różny przebieg w zależności od dnia tygodnia. Na przykład w poniedziałek składa się z 99 etapów i wygląda tak: w pierwszym etapie otwierane są wszystkie drzwi, w drugim zamykane te z parzystymi numerami, w trzecim otwiera się drzwi z numerami podzielnymi przez 3, w czwartym zamyka te z numerami, które dzielą się przez 4 itd.; zatem w każdym k-tym etapie zmienia się stan drzwi z numerem podzielnym przez k. W efekcie, po zakończeniu poniedziałkowej manipulacji otwarta pozostaje tylko część drzwi. Ile i które?

Każda liczba ma co najmniej dwa dzielniki naturalne zwane trywialnymi – jeden i samą siebie. Jeśli ma tylko te dwa, jest liczbą pierwszą (np. 3, 47, 809, 5261); jeśli więcej – liczbą złożoną. Mnożąc przez siebie dwie liczby pierwsze, otrzymamy liczbę złożoną półpierwszą, która zwykle ma cztery dzielniki, a czasem trzy. Ogólnie: każda liczba złożona jest iloczynem liczb pierwszych i znacznie częściej ma parzystą niż nieparzystą liczbę dzielników. To stwierdzenie stanowi poniedziałkowy klucz do „otwartych drzwi”.

Niełatwo ustalić liczbę dzielników wielocyfrowej liczby n. Bez komputerowego wsparcia nie ma sensu rozstrzygać, na przykład, która liczba ma więcej dzielników – a=12345678 czy b=87654321 – i o ile więcej. Przy wielokrotnie większych liczbach nawet komputer może nie sprostać wyzwaniu ze względu na zbyt długi czas pracy.

Liczbę dzielników liczby n oznacza się grecką literą tau (t), ale nie jest znany prosty wzór, określający bezpośrednio zależność między n a t(n). Funkcja t(n) „skacze” nieregularnie między szczytami a przepaściami (czerwone punkty na niebieskiej linii na rys. 1) – dlatego można ją nazwać dyskretną, czyli nieciągłą. Średnia wysokość szczytów rośnie, ale najgłębsze przepaści pozostają na stałym poziomie równym 2, odpowiadającym liczbom pierwszym. Skuteczna metoda, umożliwiająca określenie wartości t(n) zaczyna się od rozłożenia n na czynniki pierwsze, czego rezultatem jest tzw. zapis kanoniczny, czyli iloczyn liczb pierwszych p równy n:

n = p₁^w1×p₂^w2×…×p_k^wk

Dzielnikami liczby n są liczby p oraz ich wszystkie różne iloczyny, w których żadna liczba p nie występuje więcej razy, niż wynosi wykładnik potęgi umieszczony przy danej liczbie w zapisie kanonicznym. Liczba dzielników wyraża się iloczynem wszystkich liczb o jeden większych od wykładników potęg, czyli: t(n) = (w₁+1)×(w₂+1)×…×(w_k+1). Na przykład w dzielnikowym „pojedynku” wspomnianych wyżej 8-cyfrowych liczb a i b zwycięża zdecydowanie – i zapewne niespodziewanie – ta mniejsza, czyli a, ponieważ: a=12345678=2¹×3²×47¹×14593¹, a więc t(b)=2×3×2×2=24, natomiast b=87654321=3²×1997¹×4877¹, czyli t(a)=3×2×2=12.

W roku 1838 niemiecki matematyk Peter Gustav Dirichlet wpadł na pomysł, który miał zaowocować wzorem na t(n), niewymagającym rozkładania n na czynniki pierwsze. Dzielniki naturalne każdej liczby n tworzą pary – ich iloczyn w danej parze równy jest n. Na przykład, dla 12 są trzy pary: (1, 12), (2, 6), (3, 4); dla 60 – sześć par: (1, 60), (2, 30), (3, 20), (4, 15), (5, 12), (6, 10). Wprawdzie kwadraty mają nieparzystą liczbę dzielników, ale „samotny” dzielnik w istocie tworzy parę bliźniaczą, np. (6, 6) w 36 lub (9, 9) w 81.

Każdą parę dzielników można potraktować jako współrzędne dwóch punktów – (x, y) i (y, x); np. (2,6) i (6,2) – w układzie kartezjańskim. Punkty odpowiadające wszystkim parom dla danego n leżą w pierwszej ćwiartce na gałęzi hiperboli o wzorze xy=n (w dalszym opisie określenie „hiperbola” będzie dotyczyło tylko tej gałęzi). Na rysunku 2 znajduje się hiperbola xy=12. Czym są oznaczone na tym rysunku czerwone punkty sieciowe, czyli punkty o współrzędnych całkowitych? Znajdujące się na hiperboli xy=12 (obwiedzione kółkami), odpowiadają oczywiście dzielnikom liczby 12, a ściślej: dzielnikom równe są współrzędne x lub y tych punktów. A pozostałe?

Gdybyśmy dorysowali w pierwszej ćwiartce jedenaście hiperbol o wzorze xy=n dla 1≤n≤11, to każda z nich przeszłaby przez inne czerwone punkty, odpowiadające parom dzielników danej liczby n, i każdy punkt znalazłby się na jakiejś hiperboli. Inaczej mówiąc, wszystkich czerwonych punktów jest tyle, ile jest w sumie dzielników liczb od 1 do 12, czyli S(12)=t(1)+ t(2)+… +t(12). W ten sposób żmudne, zwłaszcza dla dużych n, zadanie rachunkowe, polegające na obliczeniu łącznej liczby dzielników n liczb od 1 do n, zmieniło się w geometryczne, które, nieco trywializując, sprowadza się do pytania: ile jest kropek na i pod hiperbolą y=n/x dla 1≤x≤n? Gdyby udało się wyprowadzić prosty wzór na liczbę kropek S(n), to wówczas, aby znaleźć t(n), wystarczyłoby obliczyć różnicę S(n)–S(n-1).

Kropki pod hiperbolą xy=n leżą na odcinkach n prostych x=k (1≤k≤n); końce odcinków wyznaczają oś x i hiperbola. Na każdym odcinku jest [n/k] kropek; nawiasy kwadratowe oznaczają, że uwzględniamy tylko całkowitą część wyniku. Liczba wszystkich kropek będzie więc sumą: S(n)=. Ten krótki wzór oznacza w praktyce długie, żmudne sumowanie ilorazów. Na przykład, dla n=12 S(n)=12/1+12/2+12/3+12/4+[12/5]+12/6+[12/7]+[12/8]+[12/9]+[12/10]+[12/11]+12/12=12+6+4+3+2+2+1+1+1+1+1+1=35. Dla większych n korzystanie z tego wzoru wymaga wsparcia komputerowego. Nietrudno jednak uczynić obliczenia nieco mniej żmudnymi po zauważeniu, że hiperbola xy=n ma oś symetrii x=y, która przecina hiperbolę w punkcie (√–n, √–n). Na rysunku 2 można w związku z tym wyodrębnić dwa przystające, zawierające taką samą liczbę kropek obszary: jeden zawarty między liniami x=0, x=n/y, x=√–n, y=0, y=n oraz drugi – między x=0, x=n, y=0, y=n/x, y=√–n. Wspólną częścią obu tych obszarów jest na rys. 2 żółty kwadrat o boku równym √–n. Wzór na liczbę kropek będzie miał, po uwzględnieniu zależności między tymi obszarami, postać:

S(n) = 2 – [√–n]². Teraz liczenie dla 12 jest krótsze: S(n)

= 2×(12/1+12/2+12/3) – [√–12]² = 2×(12+6+4) – 3² = 44 – 9 = 35.

Ostatni wzór można przekształcić do postaci teoretycznie wygodniejszej do stosowania, ale przekształcenie jest matematycznie zbyt skomplikowane, aby je tu przedstawiać, a sam wzór nie gwarantuje dokładnego wyniku i wiąże się z dotychczas nierozwiązanym zagadnieniem, tzw. problemem dzielników Dirichleta. Ogólna, uproszczona postać tego wzoru wygląda następująco: S'(n)=nlnn+cn+a_n. Symbol c równy jest w przybliżeniu 0,15443 (dwukrotność tzw. stałej Eulera minus jeden), zaś a_n oznacza funkcję wykładniczą, w której dokładna wartość podstawy i wykładnika potęgi pozostaje zagadką. Pierwszy i największy składnik wzoru stanowi wynik całkowania funkcji y=n/x w przedziale [1, n] i dla n=12 równy jest polu pod hiperbolą otoczonemu purpurową linią na rys. 3.

Żółte pole na tym rysunku, złożone z jednostkowych kwadratów, równe jest co do wartości liczbowej S(12)=35. Zatem drugi i trzeci składnik wzoru służą niejako zrównaniu powierzchni wyznaczonej purpurową linią z powierzchnią żółtych kwadratów. Dirichlet przyjął, że a_n=√–n, co dla n=12 daje właściwą wartość, czyli [S'(n)]=S(n), ale np. dla n=100 już tylko przybliżoną (485 zamiast 482). Uporanie się z problemem dzielników Dirichleta polega więc na doprowadzeniu składnika a_n do takiej postaci, aby wzór był „skuteczny” dla każdego n (skuteczność jest kwestią umowną; ogólnie oznacza minimalny błąd, czyli jak najmniejszą różnicę między S(n) a [S'(n)]).

Pytanie o liczbę z największą liczbą dzielników ma sens, gdy podany jest jakiś dodatkowy warunek, dotyczący szukanej liczby, zazwyczaj przedział, w którym ma występować. Na przykład, w zakresie od 1 do 1000 palmę pierwszeństwa w konkurencji t(n) dzierży 840 z 32 dzielnikami. Istnieje w związku z tym pojęcie liczb najbardziej złożonych, czyli najbogatszych w dzielniki. Każda z nich ma więcej dzielników niż każda mniejsza od niej. Taką liczbą jest więc również zaczynające ciąg liczb złożonych 2, a kilku następnym odpowiadają kolejne coraz wyższe szczyty na rys. 1, połączone szarą linią. Na tzw. długiej liście zadań zgłoszonych na Międzynarodową Olimpiadę Matematyczną w 1983 roku znalazło się następujące: która z liczb mniejszych od 1983 ma największą liczbę dzielników?

W wysokogórskim krajobrazie na rys. 1 na uwagę zasługują także obwiedzione żółtą linią tarasy. Każdy z nich istnieje, ponieważ t(n) dwu lub więcej kolejnych liczb jest jednakowe. Najwięcej jest tych najkrótszych, 2-liczbowych; brytyjski matematyk Roger Heath-Brown udowodnił w 1984 roku, że jest ich nieskończenie wiele. Na rys. 1 zmieścił się też pierwszy taras 3-liczbowy – tworzą go 33, 34 i 35, t(n)=4; następne 3-liczbowe zaczynają się od 85, 93, 141, 201, 213, 217, 230, 242, 243, 301…. Pierwszy 4-liczbowy ma na początku 242 (t(n)=6), 5-liczbowy – 11 605 (t(n)=8), 6-liczbowy – 28 374 (t(n)=8)… A jaki taras jest najdłuższy?

Paul ErdÖs wysunął hipotezę, że długość tarasów jest nieograniczona, choć tworzące je liczby szybko stają się gigantyczne. Najdłuższy znany taras znaleziony w minionym roku przez rosyjskiego matematyka Władimira Lecko tworzy 14 kolejnych liczb 35-cyfrowych. Oto pierwsza z nich: 25 335 305 376 270 095 455 498 383 578 391 968. Wszystkie mają po 24 dzielniki. Wiele wskazuje na to, że teoretycy liczb na tym tarasie nie spoczną.

Zadania

1. Jaka liczba podzielna przez 2 i 9 ma dokładnie 14 dzielników?

2. Jeśli do pól kwadratu 3×3 wpiszemy dziewięć różnych cyfr – od 1 do 9 – to utworzą one w trzech wierszach i trzech kolumnach liczby 3-cyfrowe. W przykładzie (rys. 4a) w wierszach są liczby 167, 258, 349, a w kolumnach – 123, 654, 789. Każda cyfra przed wierszem (nad kolumną) oznacza, ile wszystkich dzielników ma liczba w danym wierszu (kolumnie). W zadaniu (rys. 4b) cyfry od 1 do 9 należy wpisać do pól kwadratu tak, aby występowała taka sama jak w przykładzie zależność między podanymi cyframi obok kwadratu, a 3-cyfrowymi liczbami, które pojawią się w kwadracie.

3. 216 jest najmniejszą liczbą, która ma następującą własność: wśród jej dzielników (1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 27, 36, 54, 72, 108, 216) można wskazać dziewięć takich, z których każdy zaczyna się inną cyfrą (także kończy się, jeśli jest jednocyfrowy). Jaka jest najmniejsza liczba o własności jakby odwrotnej: wśród jej dzielników można wskazać dziesięć takich, z których każdy kończy się inną cyfrą (i zaczyna się, jeżeli jest jednocyfrowy)?

4. Na stole leży dziesięć żetonów oznaczonych kolejnymi liczbami od 1 do 10. Dwaj gracze na przemian zabierają po jednym. Nie wolno wziąć żetonu z liczbą, która jest dzielnikiem liczby usuniętej ze stołu w jednym z poprzednich ruchów. Przegrywa ten, kto w swoim ruchu nie może zabrać żadnego żetonu. Żeton z jaką liczbą należy wziąć w pierwszym ruchu, aby zagwarantować sobie wygraną?

Rozwiązania prosimy nadsyłać do 28 lutego br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 2/17, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02-697 Warszawa. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Ułamki filozofii Leszka Kołakowskiego ufundowaną przez wydawnictwo Prószyński Media.

***

Rozwiązania zadań z numeru grudniowego

1. Rys. 5.

2. Rys. 6 (jedno z dwóch symetrycznych rozwiązań).

3. Rys. 7.

Za poprawne rozwiązanie przynajmniej dwu zadań książkę Lisy Randall Ciemna materia i dinozaury ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Marcin Chomenko z Gdańska, Tomasz Kowalczyk z Ostrowska, Magdalena Pospieszałowska z Krakowa, Janusz Włodarczyk z Będzina, Hubert Wastkowski z Milanówka.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.