Na tropie AP 26

Data ostatniej modyfikacji:
2010-04-14
Autor: 
Małgorzata Mikołajczyk
pracownik IM UWr
Dział matematyki: 
algorytmika
teoria liczb
Poziom edukacyjny: 
gimnazjum
szkoła średnia z maturą
szkoła profilowana zawodowa

Wiadomo, że liczby pierwsze są rozłożone wśród liczb naturalnych dość chaotycznie. Na przekór temu matematycy postanowili szukać regularnych układów liczb pierwszych, a za najbardziej regularne uznali serie liczb leżących w jednakowych odstępach jedna od drugiej, czyli tworzące ciągi arytmetyczne.

Co już wiadomo

Nie istnieje nieskończony ciąg arytmetyczny złożony z liczb pierwszych.
Uzasadnienie: Niech liczba pierwsza p będzie pierwszym wyrazem takiego ciągu, a r jego różnicą (czyli odstępem między kolejnymi wyrazami). Wśród dalszych wyrazów ciągu znajdziemy liczby: p+pr, p+2pr, p+3pr..., a one są podzielne przez p i większe od p, więc nie mogą być pierwsze.

Istnieje nieskończenie wiele ciągów arytmetycznych długości 3.
Twierdzenie to udowodnił w 1939 roku duński matematyk Johannes van der Corput. Przez następnych 65 lat nie udało się podobnego faktu wykazać dla ciągów czterowyrazowych i dłuższych.

Istnieją dowolnie długie (ale skończone) ciągi arytmetyczne złożone z liczb pierwszych.
Taką hipotezę sformułowali jeszcze w 1770 roku Lagrange i Waring, ale udowodnili ją dopiero w 2004 roku dwaj młodzi matematycy: Brytyjczyk Ben Green i Australijczyk chińskiego pochodzenia Terence Tao. Jest to tzw. dowód egzystencjalny - nie podaje sposobu konstruowania takich ciągów, a jedynie stwierdza ich istnienie.

Dla każdego k istnieje nieskończenie wiele ciągów arytmetycznych długości k złożonych z liczb pierwszych.
Uzasadnienie: Wynika to wprost z twierdzenia Greena-Tao. Na przykład dla k = 4 możemy uwzględnić także wszystkie dłuższe ciągi, a skoro istnieją dowolnie długie, to czterowyrazowych musi być nieskończenie wiele.

Najdłuższy znany ciąg kolejnych liczb pierwszych tworzących ciąg arytmetyczny liczy 10 wyrazów.
Ciąg ten znaleziono w 1998 roku. Zaczyna się liczbą o 93 cyfrach: 100 9969724697 1424763778 6655587969 8403295093 2468919004 1803603417 7589043417 0334888215 9067229719, a jego różnica wynosi 210.

Najdłuższy znany ciąg arytmetyczny liczb pierwszych liczy 25 wyrazów.
Został odkryty 17 maja 2008 roku dzięki współpracy matematyka z Uniwersytetu Wrocławskiego - Jarosława Wróblewskiego - i informatyka z Izraela - Raanana Chermoniego. Dokładniej rzecz ujmując, Chermoni wykonał obliczenia, wykorzystując metodę opracowaną przez wrocławianina.

Pierwszy wyraz tego ciągu to p = 6 171 054 912 832 631, a każdy kolejny jest
większy od poprzedniego o r= 81737658082080, czyli 366384·23#, gdzie symbol n# (czytaj: en primorial) oznacza iloczyn liczb pierwszych nieprzekraczających n (np. 10# = 210).

Odkrycie tego ciągu wymagało w sumie 57 lat pracy procesora ósmej generacji Athlon-64, jednak praca ta dzięki współpracy matematyka tworzącego algorytm i programisty z jego sprzętem została usprawniona przez podzielenie jej między wiele maszyn liczących i w rzeczywistości zajęła mniej niż rok.

Poszukiwanie AP 26

Aby pobić rekord i znaleźć ciąg o 26 wyrazach, potrzebnych będzie najprawdopodobniej ponad 1000 lat działania tego samego procesora, tym bardziej potrzeba więc udziału wielu komputerów. Mogłoby zająć to wręcz kilka minut, gdyby użytych było jednocześnie kilkaset milionów odpowiedniej klasy maszyn, ale uprzednio trzeba by było i tak właściwie podzielić między nie całą pracę.

Pod koniec grudnia 2008 roku problemem tym zainteresowała się grupa matematyków i informatyków z PrimeGrid. Jest to międzynarodowy projekt internetowy zarządzany przez Uniwersytet w Kalifornii, zajmujący się wykonywaniem obliczeń rozproszonych, zwłaszcza dotyczących liczb pierwszych. Obliczenia są wykonywane przez komputery domowe zwykłych użytkowników na całym świecie, którzy zdecydują się ofiarować do tego celu wolne moce swoich komputerów, poprzez zainstalowanie odpowiedniego oprogramowania (patrz http://www.primegrid.com/). Serwer PrimeGrid rozdziela przez internet pracę i zbiera wyniki.

Jednym z najnowszych projektów PrimeGrid jest AP26 Search, którego celem jest znalezienie wspólnymi siłami internautów 26-wyrazowego postępu arytmetycznego złożonego z liczb pierwszych - w skrócie AP26 (arithmetic progression of 26 primes). Wykorzystywany do tego celu program komputerowy opiera się na oryginalnym pomyśle Jarosława Wróblewskiego, przerobionym na potrzeby pracy rozproszonej przez Geoffa Reynoldsa.

W projekcie może wziąć udział każdy posiadacz komputera z Linuxem lub Windowsem. Szczegóły można znaleźć na stronie http://www.primegrid.com/forum_forum.php?id=38 lub na polskojęzycznym forum http://www.boincatpoland.org/smf/primegrid/.

BOINC@Poland wchodzi do gry
8 kwietnia 2009 AP26 Search uczynił najważniejszy krok na drodze do znalezienia postępu 26-wyrazowego, mianowicie odkrył drugi postęp 25-wyrazowy. Ma on mniejszy wyraz początkowy i większy końcowy od poprzedniego.

an = 2 960 886 048 458 003 + 2346233 · 23# · n, dla n\in{0, 1, ..., 24}.

Nietypowa jest osoba odkrywcy, czyli właściciela komputera, który dokonał tego odkrycia. Jest nim zespół BOINC@Poland zrzeszający użytkowników, którzy decydują się na wykorzystanie wolnych mocy swoich komputerów dla celów obliczeniowych w różnorakich projektach. Zespół ten jest światowym liderem projektu AP26 Search. Pod względem wykonanej pracy i dotychczasowych odkryć góruje nad resztą świata (razem wziętą). Czekamy na dalsze wyniki!

Jest AP 26

12 kwietnia 2010, niespełna rok po znalezieniu AP25, jeden z członków zespołu francuskiego pracującego w projekcie PrimeGrid znalazł postęp 26-wyrazowy. Oto on:

43142746595714191+23681770·23#·n  dla n = 0 , ..., 25. 

Czekamy na AP 27!!!

 

Przydatne linki
http://users.cybercity.dk/~dsl522332/math/aprecords.htm
http://www.primegrid.com/forum_thread.php?id=1246&nowrap=true#14757
http://www.boincatpoland.org/wiki/8_kwietnia_2009_SKB%40P_znalaz%C5%82_r...

Poprawka

PrimeGrid jest projektem, którego "siedziba" mieści się na Litwie. Korzysta on za to z oprogramowania do koordnacji obliczeń rozproszonych pod nazwą BOINC, które rzeczywiście powstaje na Uniwersytecie Kalifornijskim w Berkeley.

n# ?

Czy możecie to lepiej wytłumaczyć, bo z przykładu wynika, że #=21 i nie wiem czy 21 jest wynikiem iloczynu dwóch liczb pierwszych 3 i 7, czyli 10#= 3*7*10 czy jeszcze inaczej. Proszę o wyjaśnienie, bo nie mogę obliczyć tego iloczynu 2346233 · 23# · n, dla n ze zbioru {0, 1, ..., 24}. I skąd 26 wyrazów? Z góry dzięki za odpowiedź.

Czytaj uważnie

Drogi Flamanie. Odpowiedzi na Twoje pytania są zawarte w tekście. Wystarczy uważnie go przeczytać. Przede wszystkim zapis "#=21" nie ma sensu, bo nie podałeś argumentu operacji #. Cytuję za tekstem: n# to iloczyn liczb pierwszych nieprzekraczających n. Zatem 10 nie może być czynnikiem liczby 10#, bo to nie jest liczba pierwsza. Mamy:
10# = 2*3*5*7 = 210,
21# = 2*3*5*7*11*13*17*19 = 9699690.
W podanym ciągu jest tylko 25 wyrazów. Powstają przez podstawienie za n kolejno liczb od 0 do 24, których jest właśnie 25. Jak podano w tekście, ciąg o 26. wyrazach jest nadal poszukiwany.

 

Powrót na górę strony