Wyścigi i animozje, czyli o dwóch osobliwościach liczb pierwszych

Liczby pierwsze od wieków stanowią jedno z najbardziej zagadkowych zagadnień matematycznych. Wprawdzie dziś dużo o nich wiemy, ale jest to wiedza zdominowana przez przybliżenia i hipotezy, jak choćby wzór na szacunkową liczbę liczb pierwszych mniejszych od x (x/lnx); dokładnej liczby w danym zakresie nie potrafimy określić wzorem, a co najistotniejsze – i co stanowi największą zagadkę – nie znamy reguły rządzącej ich rozmieszczeniem prostszej niż sposób selekcji zwany sitem Eratostenesa (usuwanie wielokrotności kolejnych liczb pierwszych) ani tym bardziej nie znamy formuły, która pozwalałaby wyznaczać kolejne liczby. Istnieją wprawdzie sążniste wzory, zasługujące raczej na miano algorytmów, ale ze względu na złożoność obliczeniową są one w szerszym zakresie niepraktyczne. W tej sytuacji nie dziwi, że niemal każda nowa informacja dotycząca liczb pierwszych budzi zainteresowanie nie tylko specjalistów. Zwłaszcza że temat zazwyczaj można przedstawić w sposób zrozumiały dla każdego, poczynając od podstawowej definicji: liczby pierwsze to takie, które nie mają dzielników właściwych, czyli są podzielne tylko przez jeden i samą siebie. Ostatnia dotychczas wzmianka, określana mianem sensacyjnej, obiegła niektóre media przed dwoma laty, a dotyczyła – ogólnie rzecz biorąc – liczb… ostatnich, a ściślej – ostatnich cyfr.

Robiące wrażenie chaotycznego lub losowego rozmieszczenie liczb pierwszych na osi liczbowej nie daje spokoju zarówno matematykom, jak i amatorom matematyki rekreacyjnej; jedni i drudzy wciąż próbują, nierzadko po omacku, doszukiwać się w nim jakichś regularności albo przynajmniej konkretów – z nadzieją, że przybliży to odkrycie „ukrytej w szaleństwie metody”. Elementarnym konkretem jest na przykład to, że ostatnią cyfrą liczb pierwszych większych niż 5 może być tylko 1, 3, 7 lub 9. Innymi słowy, liczba pierwsza modulo 10 (p mod 10), czyli reszta z dzielenia p przez 10, jest zawsze jedną z tych czterech cyfr. Jeżeli ciąg liczb pierwszych zastąpić ciągiem ich ostatnich cyfr, to jego sto początkowych wyrazów (bez oddzielających je przecinków) będzie wyglądać jak na rys. 1a.

Tabela 1

Specjalistów w dziedzinie teorii liczb, teorii prawdopodobieństwa lub statystyków, czy choćby miłośników zagadek liczbowych, interesuje w utworzonym ciągu to samo – na przykład: ile razy w różnych zakresach liczb naturalnych od 1 do n występuje każda z cyfr. Do n=100 (żółty fragment na rys. 1a) jedynka pojawia się 5 razy, trójka – 7, siódemka – 6, a dziewiątka – 5 razy. Statystyki dla dłuższych odcinków osi liczbowej przedstawione są w tabeli 1; koniec niebieskiego fragmentu na rys. 1a jest końcem zakresu do n=200, koniec różowego – do n=500. Śledząc kolejne etapy tego „wyścigu” czterech wartości p mod 10, można zauważyć, że cały czas prowadzą trójka i siódemka. Prowadzenie jest nieznaczne, ale wyraźne i zagadkowe, bo zgodnie z teorią liczb pierwszych wszystkie cztery wartości mają na każdym dystansie taką samą szansę na zwycięstwo, a więc powinny iść łeb w łeb.

Matematycy „bawili się” w organizowanie podobnych wyścigów liczb pierwszych dla paru innych wartości modulo, o ile było to możliwe, czyli gdy do współzawodnictwa kandydowały co najmniej dwie wartości. Na przykład, dla dwójki do startu nie dojdzie, bo modulo 2 każdej liczby nieparzystej równe jest 1. Startujący w pozostałych gonitwach (p mod q) znajdują się w tabeli 2. Warto przy okazji zauważyć, że liczby q i p mod q muszą być względnie pierwsze, czyli nie mogą mieć wspólnych dzielników (dlaczego?).

Tabela 2

Przebieg niektórych wyścigów okazał się równie zaskakujący, jak w przypadku modulo 10, czyli pewne wartości, niejako wbrew teorii, cały czas pozostawały w tyle za innymi. Było to wyraźnie widoczne przy modulo 3, 4 i 8, co przedstawia tabela 3: każda żółta kolumna oznacza outsidera w danym wyścigu modulo q.

Tabela 3

Matematycy zauważyli ten „wybryk natury” już w połowie XIX wieku, ale nie potrafili lub nie próbowali go wówczas wytłumaczyć. Dopiero kilkadziesiąt lat później okazało się, że odpowiedzialne za to są kwadraty liczb pierwszych. Jeżeli w konkurencji p mod q startują liczby a₁, a₂, a₃, …, a_n, to pozostawać w tyle za innymi będą te, które są takie same jak wartości p² mod q. Wszystkie te sytuacje obejmuje tabela 4. Wynika z niej, na przykład, że w gonitwie p mod 6 outsiderem będą jedynki, bo p² mod 5 = 1, a w gonitwie p mod 10 jedynki i dziewiątki, co widoczne jest w tabeli 1.

Tabela 4

Co ciekawe, ta anomalia nie jest sprzeczna z ogólnym twierdzeniem o równych szansach każdej z liczb, startujących w konkretnej konkurencji p mod q. Ściślej, zgodnie z tym twierdzeniem iloraz każdej pary tych liczb dąży do 1, gdy n dąży do nieskończoności. Stąd wniosek, że na bardzo długim dystansie początkowy słabeusz powinien przynajmniej zrównać się z dotychczasowym liderem. I rzeczywiście tak się dzieje. W gonitwie p mod 4 4k+1 wychodzi na prowadzenie na liczbie 26 861 (krótkie, „punktowe” remisy zdarzają się wcześniej – przy 5, 17, 41 i 461) i natychmiast je traci, aby odzyskać aż na 616 841. Znacznie dłużej musi czekać na przodowanie zawodnik 3k+1 w wyścigu p mod 3 – aż do liczby 608 981 813 029; natomiast 8k+1 w konkurencji p mod 8 zostaje liderem dopiero przy gigantycznej liczbie pierwszej rzędu 10²⁸.

Jeszcze w połowie XX wieku wspomniane wyżej „twierdzenie o równych szansach” było hipotezą. Pojawiła się nawet przeciwna hipoteza, że w wyścigu liczb p mod q zawsze jakiś zawodnik stoi na straconej pozycji. Dopiero dzięki rozwojowi elektronicznej techniki obliczeniowej okazało się, że tę przeciwną hipotezę należy podporządkować tzw. prawu małych liczb, czyli jest ona prawdziwa w ograniczonym zakresie, gdy dotyczy względnie małych wartości. Wiele wskazuje na to, że podobna sytuacja występuje w przypadku wzmiankowanej na początku sensacyjnej informacji sprzed dwóch lat, dotyczącej liczb pierwszych. Oto dwaj matematycy ze Stanford University, Kannan Soundararajan i Robert Lemke Oliver, postanowili sprawdzić, czy słuszne jest rozpowszechnione wśród teoretyków liczb traktowanie sekwencji liczb pierwszych jako „pseudolosowej”, czyli takiej, w której powtarzalność własności poszczególnych wyrazów jest w znacznym stopniu losowa, a więc podlega teorii prawdopodobieństwa. Zajęli się, podobnie jak w przypadku opisanych wyżej „wyścigów”, ostatnimi cyframi liczb pierwszych, ale interesował ich inny przejaw losowości: jeśli jakaś liczba pierwsza kończy się określoną cyfrą, to każda z cyfr – 1, 3, 7, 9 – ma taką samą szansę, równą 25%, aby pojawić się na końcu następnej liczby pierwszej. Idąc śladem matematyków, możemy to sprawdzić w minimalnym, a więc mało miarodajnym zakresie, obejmującym ciąg na rys. 1. złożony z końcowych cyfr stu kolejnych liczb pierwszych, a więc z ich 96 par …a/…b (trzy początkowe cyfry pomijamy). Wyniki znajdują się w drugiej i trzeciej kolumnie tabeli 5. Natomiast w ostatniej kolumnie tej tabeli są efekty komputerowych obliczeń uzyskane przez matematyków (procentowy udział każdej pary …a/…b w ogólnej liczbie par z taką samą cyfrą …a), ale dla zakresu obejmującego sto milionów liczb pierwszych.

Tabela 5

Z porównania procentowych wartości w kolumnach trzeciej i czwartej można wnioskować, że udział poszczególnych par rzeczywiście zmierza do spodziewanych 25%, co zresztą potwierdzają obliczenia dla większego niż 10⁸ zakresu liczb pierwszych. W tym kontekście zaskakujące są jednak wartości oznaczone żółtym kolorem. Wynika z nich, że w uwzględnionym w tabeli zakresie wyraźnie rzadziej zdarza się, aby dwie kolejne liczby pierwsze były zakończone taką samą cyfrą (zielone na rys. 1b). Teoretycy liczb przyjęli ten fakt z niedowierzaniem, stwierdzając, że ta animozja przypomina odpychanie się jednoimiennych biegunów magnesu. Wyjaśnienie tego zjawiska dla względnie małych liczb wydaje się proste: liczby pierwsze są wówczas rozmieszczone na tyle gęsto, że jest spora szansa, iż między dwiema kolejnymi, zakończonymi taką samą cyfrą, na osi liczbowej pojawi się chociaż jedna inna liczba pierwsza. Dla dużych liczb przyczyna „odpychania” pozostaje jednak zagadką, choć matematycy doszukują się przynajmniej częściowego wyjaśnienia w tzw. hipotezie Hardy’ego-Littlewooda o k-krotkach. Zgodnie z tą hipotezą liczby pierwsze rozmieszczone są na osi liczbowej grupami (krotkami) w ściśle określonych odstępach, które są liczbami parzystymi. Gdy odstęp jest jeden i wynosi 2, krotką są liczby bliźniacze (np. 11 i 13). Dla dwóch kolejnych odstępów równych 4 i 2 krotkę tworzą np. liczby 7, 11, 13. Hipoteza określa częstość występowania poszczególnych rodzajów krotek na osi liczbowej, co z kolei przekłada się na zależność między końcowymi cyframi tworzących je liczb (te, między którymi jest odstęp równy 10 lub wielokrotności 10, są rzadsze). Trzeba jednak pamiętać, że jest to tylko hipoteza, więc nie ma pewności czy lub w jakim stopniu wpływa na „odpychanie”.

Do zainteresowania się losowością rozkładu liczb pierwszych skłoniło Soundararajana i Olivera wysłuchanie wykładu ściśle związanego z matematyką rekreacyjną, dotyczącego zastosowania teorii prawdopodobieństwa do gry „kamień, nożyce, papier”. Konkretnie była to podana w trakcie wykładu informacja na temat wariantu mało znanego paradoksu zwanego grą Penneya. Wariant ten polega na rzucaniu monetą przez dwie osoby – A i B – do momentu, aż któraś z nich uzyska swój określony na wstępie wynik dwóch kolejnych rzutów. Gracz A wygrywa, gdy wyrzuci orła po wyrzuceniu reszki, B – gdy w jego dwóch kolejnych rzutach wypadną dwa orły. Okazuje się, że wbrew intuicji szanse stron na zwycięstwo nie są równe – wyraźnie większe ma A. Ściślej: średnio cztery rzuty wystarczą osobie A, aby pojawił się jej układ, natomiast B będzie potrzebowała średnio sześciu rzutów. Łatwo przekonać się o tym samemu.

Soundararajan postanowił sprawdzić, czy podobne dziwne zjawisko nie dotyczy końcówek liczb w ciągu liczb pierwszych zapisanych w systemie trójkowym, w którym mniej więcej połowa liczb kończy się jedynką, a połowa dwójką. Okazało się, że „magia” działa także w tym przypadku – różne cyfry na końcu dwu kolejnych liczb występują ponad dwukrotnie częściej niż takie same. I tak to się zaczęło…

Zadania

1. Trzycyfrowa liczba pierwsza jest sumą trzech dwucyfrowych liczb pierwszych. Jakie cztery liczby tworzą to dodawanie, jeśli występuje w nim osiem różnych cyfr, w tym cztery parzyste?

2. Z czterech możliwych cyfr – 1, 3, 7, 9 – tą, która w ciągu liczb pierwszych pojawia się na końcu liczby najpóźniej, jest ta, która sama liczbą pierwszą nie jest, czyli 9 w 19; przed nią pojawiają się kolejno 3, 7 (jako liczby jednocyfrowe) i 1 w 11. Możliwych dwucyfrowych końcówek liczb pierwszych, które same nie są liczbami pierwszymi, jest oczywiście więcej – piętnaście: 21, 27, 33, 39, 49, 51, 57, 63, 69, 77, 81, 87, 91, 93, 99. Która z nich pojawia się po raz pierwszy w ciągu liczb pierwszych na końcu liczby najpóźniej?

3. W ciągu 137909… każda kolejna cyfra, zaczynając od piątej, jest ostatnią cyfrą sumy czterech poprzednich cyfr. Czy w ciągu tym pojawi się utworzona przez trzy kolejne cyfry liczba 102? Odpowiedź proszę krótko uzasadnić.

4. Zbiór liczb {1, 3, 7, 9} ma następującą własność: suma każdych trzech liczb z tego zbioru jest liczbą pierwszą. Proszę podać przykład innego zbioru o takiej własności, niezawierającego liczby jednocyfrowej.

Rozwiązania prosimy nadsyłać do 31 lipca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 07/18, lub listownie: Świat Nauki, ul. Gintrowskiego 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ą Edycja genów. Władza nad ewolucją Jennifer A. Doudny i Samuela H. Sternberga ufundowaną przez wydawnictwo Prószyński Media.

***

Rozwiązania zadań z numeru majowego

1. Zakładając, że hipoteza Goldbacha jest prawdziwa, możemy napisać, że dla każdej liczby n≥2 istnieją takie liczby pierwsze p i q (np. p≤q), że 2n=p+q. Ponieważ p=n-k, a q=n+k dla jakiegoś 0≤k≤n-2, więc n²-k²=pq.

2. Odgadywane liczby – 4 i 13.

3. 3+5=8 i 29+17=46 lub 3+5=8 i 29+41=70.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Nicka Sousanisa Odpłaszczenie, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Jacek Chenczke z Warszawy, Hieronim Kubica z Krakowa, Norbert Radomski z Wrocławia, Norbert Sitko z Krakowa i Piotr Stefański z Krakowa.

Sprostowanie

W numerze kwietniowym zamieszczone było poniższe zadanie.

„Liczba dzielników liczby A wyraża się liczbą oznaczającą pewien miniony rok XXI wieku. Który to rok i o jaką liczbę A chodzi, jeśli jest ona najmniejszą z możliwych?”

Podane w numerze czerwcowym rozwiązanie (rok 2016, A=139 675 536 000) – jest częściowo błędne, tzn. rok jest właściwy, ale najmniejsza liczba A wynosi 4 655 851 200.

***

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.