KOD LICZB PIERWSZYCH

Liczby pierwsze – tajemnicze, fascynujące i nieodłączne od historii matematyki. Od starożytności aż po współczesne czasy, matematycy próbują rozwikłać ich zagadki, odkrywając tym samym wiele istotnych teorii i twierdzeń.

Przedstawione poniżej informacje pozwolą nam poznać zasadę jak powstają liczby pierwsze oraz przewidzieć ich bezbłędne występowanie z pominięciem jakichkolwiek działań związanych z testem pierwszości. W skrócie poznamy od dawna poszukiwany kod liczb pierwszych.

WZÓR LICZB PIERWSZYCH

Poniższy wzór definiuje zbiór liczb pierwszych:

Poniżej znajduję się zooptymalizowany wzór do wyznaczania liczb pierwszych do danego zakresu:

Skrypt w Python odzwierciedlający powyższy wzór dla x = 1,000,000:

x = 1000000

def generate_sieve(x):
    sieve = [False] * (x + 1)

    A = {2, 3, 5}
    for num in A:
        if num <= x:
            sieve[num] = True

    k_B_max = y + 1
    for k in range(1, k_B_max):
        if k % 10 not in {4, 9}:
            val = 6 * k + 1
            if val <= x:
                sieve[val] = True

    k_C_max = y + 2
    for k in range(2, k_C_max):
        if k % 10 not in {1, 6}:
            val = 6 * k - 1
            if val <= x:
                sieve[val] = True

    k_DE_max = x // 42
    for k1 in range(1, k_DE_max):
        if k1 % 10 in {4, 9}:
            continue
        n = 6 * k1 + 1
        max_k2 = x // n + 2
        for k2 in range(1, max_k2):
            if k2 % 10 not in {1, 6}:
                val_D = n * (6 * k2 - 1)
                if val_D <= x:
                    sieve[val_D] = False
            if k2 % 10 not in {4, 9}:
                val_E = n * (6 * k2 + 1)
                if val_E <= x:
                    sieve[val_E] = False

    k_F_max = x // 66
    for k1 in range(2, k_F_max):
        if k1 % 10 in {1, 6}:
            continue
        n = 6 * k1 - 1
        max_k2 = x // n + 2
        for k2 in range(2, max_k2):
            if k2 % 10 in {1, 6}:
                continue
            val = n * (6 * k2 - 1)
            if val <= x:
                sieve[val] = False

    return sieve

y = x // 6

sieve = generate_sieve(x)
P = {i for i, is_true in enumerate(sieve) if is_true}

with open('prime.txt', 'w') as file:
    for number in sorted(P):
        file.write(f"{number}\n")

Wersja uproszczona skryptu:

x = 1000000

def generate_set_B(x):
    B = set()
    for k in range(1, k_B_max):
        if k % 10 not in {4, 9}:
            val = 6 * k + 1
            if val <= x:
             B.add(val)
    return B

def generate_set_C(x):
    C = set()
    for k in range(2, k_C_max):
        if k % 10 not in {1, 6}:
            val = 6 * k - 1
            if val <= x:
             C.add(val)
    return C

def generate_sets_D_and_E(x):
    D, E = set(), set()
    for k1 in range(1, k_DE_max):
        if k1 % 10 in {4, 9}:  
            continue
        n = 6 * k1 + 1
        max_k2 = k_max * n + 2
        for k2 in range(1, max_k2):
            if k2 % 10 not in {1, 6}:  
                val_D = n * (6 * k2 - 1)
                if val_D <= x:
                 D.add(val_D)
            if k2 % 10 not in {4, 9}:
                val_E = n * (6 * k2 + 1)
                if val_E <= x:
                 E.add(val_E)
    return D, E

def generate_set_F(x):
    F = set()
    for k1 in range(2, k_F_max):
        if k1 % 10 in {1, 6}:
            continue
        n = 6 * k1 - 1
        max_k2 = x // 6 * n + 2
        for k2 in range(2, max_k2):
            if k2 % 10 in {1, 6}:
                continue
            val = n * (6 * k2 - 1)
            if val <= x:
             F.add(val)
    return F

def save_to_file(filename, data):
    with open(filename, 'w') as file:
        for number in sorted(data):
            file.write(f"{number}\n")

k_max = x // 6
k_B_max = k_max + 1
k_C_max = k_max + 2
k_DE_max = x // 42
k_F_max = x // 66

A = {2, 3, 5}
B = generate_set_B(x)
C = generate_set_C(x)
D, E = generate_sets_D_and_E(x)
F = generate_set_F(x)

P = (A | B | C) - (D | E | F)

save_to_file('prime.txt', P)

Zbiór A zawiera liczby 2, 3 i 5.
Zbiór B zawiera liczby w postaci 6k+1 z pewnymi wyjątkami do ustalonego zakresu k.
Zbiór C zawiera liczby w postaci 6k-1 z pewnymi wyjątkami do ustalonego zakresu k.
Zbiór D zawiera iloczyny wszystkich możliwych kombinacji liczb ze wzorów 6k-1 oraz 6k+1 do ustalonego zakresu k.
Zbiór E zawiera iloczyny wszystkich możliwych kombinacji liczb ze wzorów 6k+1 do ustalonego zakresu x.
Zbiór F zawiera iloczyny wszystkich możliwych kombinacji liczb ze wzorów 6k-1 do ustalonego zakresu k.

Jak widzimy po usunięciu ze zbiorów A∪B∪C wszystkich liczb które znajdują się w zbiorach D∪E∪F otrzymamy zbiór P, który zawiera tylko liczby pierwsze do ustalonego zakresu x.

Liczby ze zbiorów D∪E∪F pozwoliłem sobie nazwać liczbami przypierwszymi o których dowiemy się więcej w dziale LICZBY PRZYPIERWSZE.

Skoro więc istnieją wzory na zbiory liczb (A∪B∪C) oraz (D∪E∪F) to logicznym staje się że zbiór liczb pierwszych P też można wyrazić w postaci wzoru.

Aby więc zobrazować w łatwy graficzny sposób te założenia użyjemy spirali Ulama, którą reprezentuje wzór:

\( P = (A \cup B \cup C) \setminus (D \cup E \cup F) \)

Następnie tworzymy spirale z naniesionymi iloczynami liczb pierwszych mających postać 6k±1, czyli z liczbami ze zbioru:

\( (D \cup E \cup F) = (A \cup B \cup C) \setminus P \)

Teraz nakładamy spirale Ulama na spirale z liczbami ze zbiorów D∪E∪F. Efekt widzimy poniżej.

Otrzymaliśmy spirale z symetrycznym układem rozłożenia liczb pierwszych i przypierwszych, czyli z liczbami ze wzoru:

\( (A \cup B \cup C) = P \cup (D \cup E \cup F) \)

Ta symetryczna struktura spirali udowadnia że występowanie liczb pierwszych jest w pełni przewidywalne i że liczby pierwsze można z całą pewnością przedstawić właśnie w formie wzoru:

\( P = (A \cup B \cup C) \setminus (D \cup E \cup F) \)

Ważnym aspektem istnienia względnie symetrycznej spirali z liczbami w postaci 6k±1 jest fakt że możemy nie tylko łatwiej przewidywać przyszłe miejsca występowania liczb pierwszych, ale także mamy ułatwioną możliwość faktoryzacji liczb przypierwszych które są wartościami n w algorytmie RSA. Szczegóły wkrótce, a na zachętę przedstawiam liczbę pierwszą o długości 101 milionów cyfr do pobrania tutaj.

Alternatywna wersja wzoru:

Skrypt w Python odzwierciedlający powyższy wzór dla x = 1,000,000:

x = 1000000

z = x // 6 + 2
y = x // 6 + 1

def generate_B(x, y):
    B = set()
    for k in range(1, y):
        p = 6 * k + 1
        if k % 10 not in {4, 9}:
            B.add(p)
    return B

def generate_C(x, z):
    C = set()
    for k in range(2, z):
        p = 6 * k - 1
        if k % 10 not in {1, 6}:
            C.add(p)
    return C

def valid_n_values(x, step, offset):
    return {n for n in range(0, x + 1, 2) if n not in {offset + 6 * k for k in range(z)}}

valid_n_D = valid_n_values(x, 2, 2)
valid_n_E = valid_n_values(x, 2, 4)

def generate_D(x, B):
    max_B = max(B)
    limit_p = int(max_B**0.5)
    D = set()
    for p in B:
        if p < limit_p:
            for n in valid_n_D:
                value = p**2 + p * n
                if value <= max_B and value % 10 != 5:
                    D.add(value)
    return D

def generate_E(x, C):
    max_C = max(C)
    limit_p = int(max_C**0.5)
    E = set()
    for p in C:
        if p < limit_p:
            for n in valid_n_E:
                value = p**2 + p * n
                if value <= max_C and value % 10 != 5:
                    E.add(value)
    return E

A = {2, 3, 5}
B = generate_B(x, y)
C = generate_C(x, z)
D = generate_D(x, B)
E = generate_E(x, C)
P = (A | B | C) - (E | D)

with open('prime.txt', 'w') as file:
    for number in sorted(P):
        file.write(f"{number}\n")

Zmodyfikowane sito Eratostenesa

Wyznaczmy na początku dwa zbiory liczbowe w którym pomijane jest ponad \( \frac{2}{3} \) liczb naturalnych i które wyznaczą wszystkie liczby pierwsze (oprócz liczb 2 i 3) oraz wyznaczą także liczby przypierwsze:

\( B = \{ 6k+1 \mid k \in \mathbb{N}, k \geq 1, k \leq x \} \)

\( C = \{ 6k-1 \mid k \in \mathbb{N}, k \geq 1, k \leq x \} \)

\( gdzie \ x \ to \ maksymalna \ wartość \ liczby \ w \ generowanym \ zbiorze \)

Liczby ze zbioru B:

{7, 13, 19 ,25, 31, 37, 43, 49, 55, 61, 67, 73, 79, 85, 91, 97, 103, 109, 115, 121, 127, 133, 139, 145, 151, 157, 163, 169, 175, 181, 187, 193, 199, 205, 211, 217, 223,…}

Liczby ze zbioru C:

{5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 95, 101, 107, 113, 119, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 191, 197, 203, 209, 215, 221,…}

Ciekawostką jest fakt że 50% wszystkich liczb w ciągu Fibonacciego stanowią liczby z omawianych wzorów 6k±1, więcej informacji w dziale CIĄG FIBONACCIEGO.

Wyznaczanie kolejnych liczb pierwszych przy pomocy funkcji trygonometrycznych.

Jak widzimy na obrazku poniżej nasze dwa zbiory z liczbami umieszczamy na osi współrzędnych X. Od punktu przecięcia osi X i Y do lewej strony osadzamy liczby ze wzoru 6k-1, natomiast w prawą stronę wstawiamy liczby ze wzoru 6k+1.

Jak widzimy powyżej wszystkie liczby naturalne na naszej osi X większe od liczby z której wyznaczyliśmy ostatnią sinusoidę (w tym przypadku większe od liczby 5), przez które przebiega sinusoida to zawsze liczby które nie są liczbami pierwszymi, gdyż są iloczynami albo kwadratami liczb pierwszych i/lub przypierwszych.

Przewidywanie występowania liczb pierwszych.

Wszystkie liczby naturalne na naszej osi X większe od liczb z których wyznaczaliśmy już sinusoidę, a jednocześnie mniejsze od wartości kwadratu następnej liczby są liczbami pierwszymi jeśli nie przecina je żadna sinusoida.

Dodatkowo wszystkie liczby naturalne na naszej osi X mniejsze bądź równe wartości z jakiej wyznaczaliśmy ostatnią sinusoidę które przecina tylko jedna sinusoida są też liczbami pierwszymi.

Czyli jak widzimy na obrazie poniżej w tym przypadku wszystkie liczby większe od 7 a mniejsze od kwadratu następnej liczby czyli 11²=121, które nie przecina żadna sinusoida są liczbami pierwszymi. Dodatkowo wszystkie liczby mniejsze bądź równe liczbie z jakiej wyznaczyliśmy ostatnią sinusoidę czyli z liczby „7” które przecina tylko jedna sinusoida są także liczbami pierwszymi.

Metodę te stosujemy trzymając się sztywno zasady że obliczenia zawsze zaczynamy od liczby „5” wyznaczając sinusoidę która przecina oś X co pięć pozycji, z liczby „7” sinusoidę przecinającą oś X co siedem pozycji, z liczby „11” sinusoidę przecinającą oś X co jedenaście pozycji, z liczby x sinusoidę przecinającą oś X co x pozycji.

Należy podkreślić że mimo iż powyższa metoda ma znamiona sita Eratostenesa to operuje tylko na \( \frac{1}{3} – 1 \) liczb naturalnych (ponieważ pomijamy \( \frac{2}{3} \) liczb naturalnych oraz liczbę 1). Dodatkowo wyróżnia się tym że definiuje bezbłędnie kolejne liczby pierwsze mniejsze od wartości kwadratu następnej liczby, bez potrzeby jakichkolwiek testów pierwszości. Im większa docelowa wartość x tym logarytmicznie mniej musimy wyznaczyć sinusoid, gdyż różnica ilości liczb między liczbą x a jej pierwiastkiem rośnie wykładniczo.

Aby znaleźć liczby pierwsze do wartości \(x\), konieczne jest wyznaczenie sinusoid z liczb do \( \sqrt{x}​ \) . Z tego wynika, że należy wygenerować jedynie \( \frac{\sqrt{x}}{3} – 1 \) sinusoid.

Dla przykładu, jeśli chcemy otrzymać liczby pierwsze w zakresie \( x\leq 1\,000\,000 \), wystarczy wygenerować sinusoidy z liczb do \( \sqrt{1\,000\,000} \) czyli do \( 1000 \) włącznie. W konsekwencji musimy wygenerować jedynie \( \frac{\sqrt{1\,000\,000}}{3} – 1 \approx 332 \) sinusoid. W efekcie, po przeprowadzeniu zaledwie \( \approx 332 \) operacji, możemy uzyskać zbiór liczb pierwszych w przedziale od 5 do 1,000,000.

Poniżej mamy prosty skrypt napisany w Python który obrazuje omawianą zasadę wyznaczania liczb pierwszych i generuje do pliku prime.txt bezbłędnie wszystkie liczby pierwsze do wartości max_num = 1000001 które musi mieć postać 6k±1

max_num = 1000001   # liczba musi mieć postać 6k±1

y = max_num - 1
 
x = -max_num

sieve = list(range(x, y, 6))

marked = [True] * len(sieve)

sqrt_max = max_num ** 0.5

for i, number in enumerate(sieve):
    if number == 1 or number == -1:
        marked[i] = False

for i, number in enumerate(sieve):
    if number == 1 or number == -1 or abs(number) > sqrt_max:
        continue
    
    offset = abs(number)

    for j in range(i + offset, len(sieve), offset):
        marked[j] = False
        
    for j in range(i - offset, -1, -offset):
        marked[j] = False

result_numbers = [abs(sieve[i]) for i, mark in enumerate(marked) if mark]

result_numbers = sorted(result_numbers)

with open("prime.txt", "w") as file:
    file.write("2\n3\n")
    for number in result_numbers:
        file.write(f"{number}\n")

Poniżej mamy zmodyfikowane sito Eratostenesa napisane w Python, które operuje tylko na liczbach ze zbiorów 6k±1 co przyśpiesza wyznaczanie kolejnych liczb pierwszych:

import numpy as np

max_num = 1000000

def generate_prime(max_num):
    prime = np.zeros(max_num + 1, dtype=np.bool_)

    prime[2] = True
    prime[3] = True

    prime[ np.arange(5, max_num + 1, 6) ] = True
    prime[ np.arange(7, max_num + 1, 6) ] = True

    limit = int(np.sqrt(max_num))
    
    p = 5
    while p <= limit:
        if prime[p]:
            prime[p*p::2*p] = False
        p += 6

    p = 7
    while p <= limit:
        if prime[p]:
            prime[p*p::2*p] = False
        p += 6

    return prime

prime = generate_prime(max_num)

prime_numbers = [str(i) for i in range(2, max_num + 1) if prime[i]]

with open('prime.txt', 'w') as file:
    file.write("\n".join(prime_numbers))

import numpy as np

max_num = 1000000

def generate_sequence(max_num):

    max_num_6 = max_num // 6
    
    sqrt_max_num = int(np.sqrt(max_num))
    
    sieve = np.ones(max_num + 1, dtype=np.bool_)
    
    target_numbers = []

    for k in range(1, max_num_6 + 1):
        num1 = 6 * k - 1
        num2 = 6 * k + 1
        
        if num1 <= max_num:
            target_numbers.append(num1)
        if num2 <= max_num:
            target_numbers.append(num2)

    for num in target_numbers:
        if num <= sqrt_max_num and sieve[num]:
            start = num * num
            step = 2 * num
            sieve[start:max_num + 1:step] = False

    prime_numbers = [num for num in target_numbers if sieve[num]]

    with open('prime.txt', 'w') as f:
        f.write("2\n3\n")
        f.write("\n".join(map(str, prime_numbers)))
        
primes = generate_sequence(max_num)

HIPOTEZY

Zastosowanie wzorów 6k±1 ogranicza poszukiwanie liczb pierwszych do zaledwie \( 26\frac{2}{3}\% \) wszystkich liczb naturalnych (przy założeniu eliminacji z naszego zbioru liczb większych od 5, które są zakończone cyfrą 5).

Wszystkie liczby pierwsze większe od 3 mają postać 6k±1.

Wszystkie kwadraty liczb pierwszych (większych od 3) zawsze mają postać 6k+1.
Kwadraty liczb pierwszych (oprócz 2 i 5) są zawsze zakończone cyfrą 1 lub 9.

Iloczyn liczb pierwszych mających postać 6k+1 zawsze znajduje się tylko w zbiorze 6k+1.

Iloczyn liczb pierwszych mających postać 6k-1 także zawsze znajduje się tylko w zbiorze 6k+1.

Jeśli jedna liczba pierwsza ma postać 6k+1, a druga 6k-1 to ich iloczyn ma postać 6k-1.

Każda liczba pierwsza (większa od 3) jest liczbą nieparzystą i jej suma cyfr wynosić może tylko
1, 2, 4, 5, 7 lub 8.

Liczby pierwsze w postaci 6k-1 mają sumę cyfr 2, 5 lub 8, natomiast liczby pierwsze w postaci 6k+1 mają sumę cyfr równą 1, 4 lub 7.

Suma cyfr liczby pierwszej (z wyjątkiem liczby 3) nigdy nie wyniesie 3, 6 lub 9.
Przypomnę, że Nikola Tesla uważał liczby 3, 6 i 9 za wyjątkowe.

Warto zwrócić uwagę że liczby przypierwsze tworzą wartość wykładnika n klucza publicznego w algorytmie szyfrowania RSA. Więcej informacji w dziale RSA.

Ten artykuł jest dostępny także w języku angielskim, kliknij tutaj.