Łowy na „merseny”

13 października 2008
Marek Penszko

Jak zapewne większość z Państwa wie, stwory zwane „mersenami” to z reguły bardzo długie węże o wzorze M=2n-1, gdzie n jest liczbą naturalną. Francuski mnich i uczony Merin Mersenne hodował je przed blisko 400 laty  i zauważył, że tylko wtedy, gdy wykładnik n jest liczbą pierwszą (p), „mersen” (M), także może być liczbą pierwszą (Mp). Może, ale nie musi. Na starcie ciągu liczb M=2p-1 dominują Mp, ale bardzo szybko stają sie unikatami w gąszczu złożonych liczb Mersenne’a (Mz) dla n=p. Czołówka ciągu wygląda tak:

3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607,
536870911, 2147483647, 137438953471, 2199023255551,
8796093022207, 140737488355327, 9007199254740991,
576460752303423487, 2305843009213693951, …

Mz wyróżnione są tłustym drukiem. Kto nie ma nic lepszego do roboty, może spróbować rozłożyć je na czynniki pierwsze;).
W miarę wędrowania wzdłuż tego ciągu na Mp trafia się coraz rzadziej. Permanentnie potykamy się natomiast o Mz, czyli „odpady”, które mało kogo interesują. Wówczas zaczyna się polowanie na Mp i jest to, co już dawno zauważono, bardzo efektywny sposób polowania na największe liczby pierwsze. Te drugie łowy trwają przynajmniej od kilkuset lat, a zdecydowanie przybrały na sile wraz z pojawieniem się „mózgów elektronowych” w latach 50.

Od 1996 roku funkcjonuje projekt obliczeń rozproszonych GIMPS, czyli ogólnoświatowa nagonka na Mp. Kto ma ochotę, może się przyłączyć do obławy, zatrudniając swój komputer, choć popularne komputery domowe mają mniejsze szanse na schwytanie delikwenta niż giganty zainstalowane w niektórych instytucjach, a od 23 sierpnia br. nadzieje ich właścicieli na zgarnięcie 100 000 dolarów ostatecznie prysły. Taką kwotę wyznaczył szeryf, czyli Electronic Frontier Foundation, za głowę i resztę cielska węża Mp złożonego z ponad 10 milionów cyfr. Właśnie 23 sierpnia jeden z łowców nagród przekroczył ten limit, czyli znalazł 45. liczbę pierwszą Mersenne’a złożoną z 12 978 189 cyfr, o czym można przeczytać na stronie projektu GIMPS. Dla tych, którym się nie powiodło, pocieszeniem są dwie informacje. Po pierwsze, nagroda jest dzielona między najaktywniejszych myśliwych, czyli mniej więcej tak, jak pula nagród w turnieju tenisowym. Po drugie: szeryf ustanowił jeszcze dwie nagrody – 150 000 dolarów za przekroczenie 100 milionów cyfr i ćwierć miliona po zaliczeniu miliardcyfrowej Mp. Warto dodać, że z wypłatą nie jest tak hop-siup. Najpierw trzeba dokładnie sprawdzić, czy z liczbą wszystko gra, a to trochę trwa.

Jaki pożytek ma ludzkość z takich i wielu podobnych, nierzadko kosztownych łowów matematycznych? Niestety, to dobre pytanie. Nie ulega wątpliwości, że praktyczne korzyści z odkrycia złóż gazu ziemnego są nieco większe, niż z odkrycia kolejnego liczbowego giganta. „Linia obrony” mniejszych korzyści oparta jest na stwierdzeniu, które przypomina sprzeciw mojej żony, gdy chcę się czegoś pozbyć przy robieniu domowych porządków: „zostaw, to się może przydać”. I rzeczywiście, czasem okazuje się przydatne.

Nie znam zadań do gimnastykowania szarych komórek, w których występują liczby Mersenne’a, ale nie odbiegnę daleko od tematu, jeśli zaproponuję Państwu zastanowienie się nad kolejną potęgową łamigłówką.

Od ponad 150 lat znana jest hipoteza, że iloczyn n kolejnych liczb naturalnych nie może być potęgą. Łatwo dowieść, że to prawda, dla n=2, 3, a nawet 4. Dalej zaczynają się dowodowe schodki, a potem schody, na szczyt których wspiął się dopiero w 1975 roku genialny Paul Erdös. Później wyszła na jaw pewna ciekawostka.
1*2*3*4=24, czyli do kwadratu (25) brakuje 1.
8*9*10*11=7920 – jeśli dodamy 1, pojawi się kwadrat (7921= 89^2)
37*38*39*40=2193360, a więc o 1 mniej od kwadratu (2193361=1481^2)
Czy ktoś odważy się udowodnić, że iloczyn czterech kolejnych liczb naturalnych zawsze będzie o jeden mniejszy od kwadratu?