Liczby pierwsze część I

XXI wiek, a my nadal nie potrafimy złamać wzoru liczb pierwszych. Jest to jedna z największych zagadek matematycznych, za pomoc w jej rozwiązaniu można otrzymać milion dolarów. Samo znalezienie liczby pierwszej, która ma więcej niż 10 000 000 cyfr, owocuje nagrodą rzędu 100 000 dolarów. Spróbujmy więc zrozumieć, w czym problem, rozwiążmy zagadkę i zgarnijmy kasiorkę! 💸

Napiszmy funkcję, która wyznacza kolejne liczby pierwsze. Sprawa jest banalnie prosta, wystarczy sprawdzić czy liczba ta nie jest podzielna przez poprzednie liczby pierwsze.

Liczby pierwsze - pierwiastki świata liczb. Ciekawe stwierdzenie które szybko znalazło swe potwierdzenie. Liczby pierwsze to najmniejsze możliwe dzielniki każdej liczby naturalnej. Liczba pierwsza 2 eliminuje nam 50% liczb naturalnych (wszystkie parzyste) następnie liczba 3 eliminuje co 3 liczbę naturalną (co druga wielokrotność trójki jest parzysta, więc eliminujemy dodatkowe 25% liczb naturalnych) i tak dalej.
Stosując powyższą funkcję, w ciągu parunastu sekund, mamy wyznaczone liczby pierwsze z przedziału 1-1 mln (mój komputer to laptop x64 z procesorem I7).
Zastosujemy dodatkową optymalizację, która zmniejszy liczbę sprawdzanych warunków.

Nie warto sprawdzać podzielności przez wszystkie poprzednie liczby pierwsze, wystarczy sprawdzić dzielniki mniejsze niż pierwiastek ze sprawdzanej liczby.

Czas wykrywania liczb pierwszych w przedziale 1-1 mln spadł stukrotnie, natomiast generacja i zapis wyników do pliku dla przedziału 1-100 mln zajęła 105 sekund (plik z samymi liczbami zajmuje 55MB i zawiera 5761445 liczb pierwszych).
Na sam koniec napiszemy jeszcze prostą funkcję która sprawdza czy podana liczba jest liczbą pierwszą. Zakładam, że badana liczba jest z przedziału 1-2^64, oraz że nie mamy wyznaczonych żadnych poprzednich liczb pierwszych. W pierwszym kroku odrzucimy wszystkie liczby parzyste oraz pominiemy sprawdzanie podzielności przez jakąkolwiek liczbę parzystą.

Przyznam szczerze, iż spodziewałem się że funkcja będzie działać dość wolno. Pozytywny test na pierwszeństwo liczby 67280421310721 trwa poniżej 0.1 sekundy.
Nie zamierzam zajmować się generacją ogromnych liczb pierwszych. Wiem, że wymaga to ogromnej mocy obliczeniowej oraz opiera się na testach probabilistycznych. W dalszych artykułach skupię się na analizie otrzymanych wyników i sprawdzeniu, czy rzeczywiście nie ma żadnego klucza przy znajdowaniu liczby pierwszej.
Pełen kod źródłowy, łącznie z zapisem znalezionych liczb do pliku tekstowego i operujący na liczbach w zakresie 2^64, znajduje się tutaj.

Liczby pierwsze część II

W części tej zamierzam przeanalizować rozkład liczb pierwszych i określić, jak rząd liczby wpływa na średni dystans między kolejnymi liczbami pierwszymi.
By wygenerować wszystkie liczby pierwsze w przedziale 1- 10 miliardów zmuszony byłem przerobić aplikacje z poprzedniej części artykułu tak aby nie trzymać wszystkich liczb pierwszych w pamięci RAM. W obecnej wersji w pamięci przechowuję tylko przedział 2-99999989, co pozwala znaleźć liczby pierwsze do 9 999 997 800 000 121. Badane liczby zajmują ponad 5GB na dysku w formacie tekstowym. Kod źródłowy aplikacji znajduje się tutaj.
Dość oczywistym wydaje się być fakt że wraz ze wzrostem rzędu liczby pierwszej średni dystans do następnego sąsiada powinien rosnąć. Wynika to z tego, że jest coraz to więcej możliwych dzielników przez jakie może dzielić się dana liczba. Z drugiej strony wraz ze wzrostem rzędu, liczba pierwsza staje się mniej znacząca (rzadziej będzie dzielnikiem).

Średni dystans między kolejnymi liczbami pierwszymi liczony w przedziałach logarytmicznych

Maksymalny dystans między kolejnymi liczbami pierwszymi, liczony w przedziałach dziesiętnych

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ciekawym jest, że w każdym analizowanym przedziale dziesiętnym najczęściej występującą odległością między kolejnymi liczbami pierwszymi jest 6

Procentowy rozkład dystansów między liczbami pierwszymi w przedziałach dziesiętnych

Rozkład dystansów między liczbami pierwszymi w przedziałach dziesiętnych

1 000 - 10 000

10 000 - 100 000

100 000 - 1 000 000

1 000 000 - 10 000 000

10 000 000 - 100 000 000

100 000 000 - 1 000 000 000

1 000 000 000 - 10 000 000 000

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

To zjawisko nie do końca rozumiem. Dlaczego najczęściej występującą liczbą pierwszą co 10 000 jest x*10 000 + 1 ?
Spadek częstości wystąpień wraz ze wzrostem dystansu jest oczywisty, biorąc pod uwagę średnie odległości między liczbami pierwszymi, ale dlaczego cyfry 1,3,7 są również na tej linii trendu?

Pierwsza liczba pierwsza co każde 10 000

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Analiza ostatniej cyfry liczby pierwszej nic nie wnosi :(

Ostatnia cyfra liczby pierwszej

Liczby pierwsze część III

Liczby pierwsze na płaszczyźnie 2D

Rozkład w rzędach

Suma w kolumnach

Suma w wierszach

Dystans między kolejnymi liczbami pierwszymi