Nowy algorytm znajdowania liczb pierwszych

[matemix]

Jakiś czas temu znalazłem pewien ciekawy sposób identyfikowania liczb pierwszych. Załóżmy, że rozważamy liczbę \(\displaystyle{ n}\). Aby sprawdzić, czy jest ona pierwsza standardowo bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{n}}\), jednak nie wykonujemy żadnych dzieleń. Konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

I obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\). Następnie obliczamy ciągi dla liczby \(\displaystyle{ n}\):

\(\displaystyle{ m(x) = \left\{\begin{array}{l} \frac {3x + n}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Tym razem rozważamy \(\displaystyle{ x \in [1,n]}\).

Mając tak poobliczanie ciągi bierzemy pod uwagę ich strukturę pod względem liczb parzystych oraz nieparzystych. Szukamy wśród struktur ciągów dla liczby \(\displaystyle{ n}\), struktur które wyznaczyliśmy dla ciągów zdefiniowanych w oparciu o liczby \(\displaystyle{ p_{1},...,p_{k}}\). Jeżeli któraś liczba \(\displaystyle{ x \in [1,n]}\) w ciągu stworzonym w oparciu o \(\displaystyle{ n}\) ma identyczną strukturę liczb parzystych i nieparzystych co \(\displaystyle{ x=1}\) w którymś z ciągów stworzonych w oparciu o liczbę \(\displaystyle{ p_{i}}\), to liczba \(\displaystyle{ p_{i}}\) dzieli bez reszty liczbę \(\displaystyle{ n}\).

Przykład:

Sprawdźmy liczbę \(\displaystyle{ 85}\). Liczby pierwsze mniejsze niż \(\displaystyle{ \sqrt{85}}\), to \(\displaystyle{ 3}\), \(\displaystyle{ 5}\), \(\displaystyle{ 7}\).

1. Obliczamy ciągi:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 3}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 5}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 7}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

\(\displaystyle{ 1,3,6,3,6,...}\)

\(\displaystyle{ 1,4,2,1,4,2,...}\)

\(\displaystyle{ 1,5,11,20,10,5,11,20,...}\)

2. Obliczamy ciągi:

\(\displaystyle{ m(x) = \left\{\begin{array}{l} \frac {3x + 85}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

dla \(\displaystyle{ x \in [1,85]}\).

3. Zauważamy, że ciąg \(\displaystyle{ 17,68,34,17,68,34,...}\) jest identyczny pod względem struktury z ciągiem \(\displaystyle{ 1,4,2,1,4,2,...}\). Ze względu na okresowość tych ciągów wiemy też, że ich kolejne elementy także się zgadzają. Zatem liczba \(\displaystyle{ 5}\) dzieli liczbę \(\displaystyle{ 85}\).


Nie podaję tu twierdzeń, ani dowodów twierdzeń na których oparłem ten algorytm. Dodatkowo można go udoskonalić zauważając, że gdy badamy jakiś ciąg dla liczby \(\displaystyle{ p_{i}}\), to jeżeli dzieli ona liczbę \(\displaystyle{ n}\), to ten ciąg musi mieć identyczną strukturę co ciąg \(\displaystyle{ m(\frac{n}{p_{i}})}\). Dlatego nie trzeba sprawdzać wszystkich ciągów \(\displaystyle{ m(x)}\), dla \(\displaystyle{ x \in [1,n]}\), a wystarczy ich sprawdzić dokładnie tyle, co jest liczb \(\displaystyle{ p_{i}}\). Oczywiście dokładne wyznaczanie \(\displaystyle{ \frac{n}{p_{i}}}\) mija się z celem, stąd, aby mimo wszystko zawęzić ilość rozważanych ciągów dla liczb z przedziału \(\displaystyle{ x \in [1,n]}\), można ten ułamek jakoś szacować, przybliżać i testować tylko liczby w pobliżu \(\displaystyle{ \frac{n}{p_{i}}}\), a nie wszystkie z przedziału \(\displaystyle{ x \in [1,n]}\).

Co myślicie o tym algorytmie? Zakładając, że jest poprawny, myślicie, że ma szanse pomóc w znajdowaniu dużych liczb pierwszych? Wszak nie wymaga on wykonywania kolejnych dzieleń, a jedynie obliczenie szeregu prostych ciągów dla testowanej liczby, oraz po jednym ciągu dla każdego z jej podejrzanych dzielników. Ponadto, nie jest konieczne obliczanie kolejnych wartości elementów ciągów (które mogą być duże), a jedynie ustalenie ich parzystości (dokładne wartości przydałoby się znać w przypadku, gdy dwa dane ciągi przez wiele iteracji są ze sobą zgodne pod względem struktury). Algorytm można też połączyć ze zwykłymi obliczeniami i używać go do wstępnego, szybkiego odrzucenia szeregu dzielników, natomiast do potwierdzenia wyłonionych dzielników może być wydajniej zastosować zwykłe obliczenia.

[Zordon]

Istnieją algorytmy wielomianowe (względem logarytmu liczby na wejściu) sprawdzające pierwszość liczby. Natomiast Twój algorytm nawet jeśli są prawdziwe wszystkie hipotezy, które przyjmujesz, ma złożoność wykładniczą i jest bardzo kiepski pamięciowo.

[matemix]

Tak podejrzewałem. W takim razie pozostanie on tylko ciekawostką. Aczkolwiek w ciągu kilku najbliższych dni dołączę jeszcze wariant tego algorytmu (a właściwie nieco odmiennego) dla liczb Mersenne'a, które można weryfikować niezmiennie w oparciu o ciąg Collatza, zamiast w oparciu o ciągi \(\displaystyle{ m(x)}\), które generują ogromne liczby i zależą od testowanej liczby \(\displaystyle{ n}\).

-- 23 lutego 2013, 04:27 --

Algorytm dla liczb Mersenna można nieco zmodyfikować i wygląda on następująco.

1. Wybieramy jakąś liczbę \(\displaystyle{ 2^n-1}\).
2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko \(\displaystyle{ n}\) elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko parzystość i nieparzystość liczb.

3. Bierzemy ciąg collatza:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 1}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

I obliczamy ciągi dla \(\displaystyle{ x \in [1, 2^n-1-\sqrt{2^n-1}]}\), jednak znów tylko \(\displaystyle{ n}\) elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach podobnie interesuje nas tylko parzystość i nieparzystość liczb.

4. Teraz szukamy w ciągach collatza ciągów identycznych pod względem struktury parzystości co ciągi wyznaczone w punkcie drugim.

5. W przypadku znalezienia ciągu collatza dla jakiejś liczby \(\displaystyle{ z}\) o identycznej strukturze co ciąg którejś z naszych liczb pierwszych \(\displaystyle{ p_{i}}\), obliczamy \(\displaystyle{ 2^n-z}\). Następnie konstruujemy ciąg:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 2^n-z}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Dla \(\displaystyle{ x=1}\) o \(\displaystyle{ n}\) elementach i sprawdzamy, czy ciąg ten jest identyczny pod względem struktury parzystości co ciąg collatza dla liczby \(\displaystyle{ 2^n-p_{i}}\). Jeżeli tak, to \(\displaystyle{ 2^n-1=p_{i} \cdot (2^n-z)}\)

Jeżeli nie znajdziemy podobnych ciągów lub nie ustalimy powyższej zależności, to liczba \(\displaystyle{ 2^n-1}\) jest liczbą pierwszą.

Przykłady:

1. Weźmy liczbę \(\displaystyle{ 2^4-1}\). Liczby pierwsze mniejsze niż pierwiastek z tej liczby, to \(\displaystyle{ 3}\).

2. \(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Skontruowany ciąg, to \(\displaystyle{ 3,6,3,6 = n,p,n,p}\).

3. Obliczamy ciągi collatza dla liczb \(\displaystyle{ x \in [1, 11]}\).

4. Zauważamy, że ciąg dla \(\displaystyle{ x=11}\) ma taką samą strukturę co ciąg dla naszej liczby pierwszej. \(\displaystyle{ 17,26,13,20 = n,p,n,p=3,6,3,6}\).

5. Obliczamy \(\displaystyle{ 2^4-11=5}\). Konstruujemy ciąg:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 5}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Wygląda on następująco: \(\displaystyle{ 4,2,1,4=p,p,n,p}\).

Obliczamy ciąg collatza dla liczby \(\displaystyle{ 2^4-3=13}\), oto on: \(\displaystyle{ 20,10,5,8=p,p,n,p}\).

Zatem: \(\displaystyle{ 2^4-1=3*(2^4-11)}\)

Co myślicie o tym algorytmie?

-- 23 lutego 2013, 05:44 --

Zapomniałem wspomnieć jeszcze o jednym fakcie który jest zaletą tego algorytmu. Ciągi collatza mają to do siebie, że zgodnie z hipotezą wszystkie się zapętlają. Oznacza, to, że po pewnym czasie stają się okresowe i wykonywanie dalszych obliczeń w powyższym algorytmie nie jest konieczne. Istnieje wzór heurystyczny który bardzo dobrze przybliża średnią długość ciągów collatza w zależności od wielkości liczby startowej:

\(\displaystyle{ t(n)=\frac {2}{ln(4/3)} \cdot ln(n)}\)

Okazuje się, że dla coraz większych przedziałów liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 2^n}\) coraz więcej liczb zapętla się dla ilości iteracji \(\displaystyle{ i<n}\), a dla \(\displaystyle{ n}\) dążącego do nieskończoności ilość tych liczb (które zapętlają się \(\displaystyle{ i<n}\) krokach) wydaje się także dążyć do nieskończoności.

-- 23 lutego 2013, 06:42 --

Tak podejrzewałem. W takim razie pozostanie on tylko ciekawostką. Aczkolwiek w ciągu kilku najbliższych dni dołączę jeszcze wariant tego algorytmu (a właściwie nieco odmiennego) dla liczb Mersenne'a, które można weryfikować niezmiennie w oparciu o ciąg Collatza, zamiast w oparciu o ciągi \(\displaystyle{ m(x)}\), które generują ogromne liczby i zależą od testowanej liczby \(\displaystyle{ n}\).

-- 23 lutego 2013, 04:27 --

Algorytm dla liczb Mersenna można nieco zmodyfikować i wygląda on następująco.

1. Wybieramy jakąś liczbę \(\displaystyle{ 2^n-1}\).
2. Bierzemy wszystkie liczby pierwsze \(\displaystyle{ p_{1},...,p_{k}}\) mniejsze niż \(\displaystyle{ \sqrt{2^n-1}}\) i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
.
.
.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{k}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Obliczamy dla każdej z funkcji ciągi dla \(\displaystyle{ x=1}\), jednak tylko \(\displaystyle{ n}\) elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko parzystość i nieparzystość liczb.

3. Bierzemy ciąg collatza:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 1}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

I obliczamy ciągi dla \(\displaystyle{ x \in [1, 2^n-1-\sqrt{2^n-1}]}\), jednak znów tylko \(\displaystyle{ n}\) elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach podobnie interesuje nas tylko parzystość i nieparzystość liczb.

4. Teraz szukamy w ciągach collatza ciągów identycznych pod względem struktury parzystości co ciągi wyznaczone w punkcie drugim.

5. W przypadku znalezienia ciągu collatza dla jakiejś liczby \(\displaystyle{ z}\) o identycznej strukturze co ciąg którejś z naszych liczb pierwszych \(\displaystyle{ p_{i}}\), obliczamy \(\displaystyle{ 2^n-z}\). Następnie konstruujemy ciąg:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 2^n-z}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Dla \(\displaystyle{ x=1}\) o \(\displaystyle{ n}\) elementach i sprawdzamy, czy ciąg ten jest identyczny pod względem struktury parzystości co ciąg collatza dla liczby \(\displaystyle{ 2^n-p_{i}}\). Jeżeli tak, to \(\displaystyle{ 2^n-1=p_{i} \cdot (2^n-z)}\)

Jeżeli nie znajdziemy podobnych ciągów lub nie ustalimy powyższej zależności, to liczba \(\displaystyle{ 2^n-1}\) jest liczbą pierwszą.

Przykłady:

1. Weźmy liczbę \(\displaystyle{ 2^4-1}\). Liczby pierwsze mniejsze niż pierwiastek z tej liczby, to \(\displaystyle{ 3}\).

2. \(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Skontruowany ciąg, to \(\displaystyle{ 3,6,3,6 = n,p,n,p}\).

3. Obliczamy ciągi collatza dla liczb \(\displaystyle{ x \in [1, 11]}\).

4. Zauważamy, że ciąg dla \(\displaystyle{ x=11}\) ma taką samą strukturę co ciąg dla naszej liczby pierwszej. \(\displaystyle{ 17,26,13,20 = n,p,n,p=3,6,3,6}\).

5. Obliczamy \(\displaystyle{ 2^4-11=5}\). Konstruujemy ciąg:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x + 5}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)

Wygląda on następująco: \(\displaystyle{ 4,2,1,4=p,p,n,p}\).

Obliczamy ciąg collatza dla liczby \(\displaystyle{ 2^4-3=13}\), oto on: \(\displaystyle{ 20,10,5,8=p,p,n,p}\).

Zatem: \(\displaystyle{ 2^4-1=3*(2^4-11)}\)

Co myślicie o tym algorytmie?

-- 23 lutego 2013, 05:44 --

Zapomniałem wspomnieć jeszcze o jednym fakcie który jest zaletą tego algorytmu. Ciągi collatza mają to do siebie, że zgodnie z hipotezą wszystkie się zapętlają. Oznacza, to, że po pewnym czasie stają się okresowe i wykonywanie dalszych obliczeń w powyższym algorytmie nie jest konieczne. Istnieje wzór heurystyczny który bardzo dobrze przybliża średnią długość ciągów collatza w zależności od wielkości liczby startowej:

\(\displaystyle{ t(n)=\frac {2}{ln(4/3)} \cdot ln(n)}\)

Okazuje się, że dla coraz większych przedziałów liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 2^n}\) coraz więcej liczb zapętla się dla ilości iteracji \(\displaystyle{ i<n}\), a dla \(\displaystyle{ n}\) dążącego do nieskończoności ilość tych liczb (które zapętlają się \(\displaystyle{ i<n}\) krokach) wydaje się także dążyć do nieskończoności.

Dodatkowo punkt piąty algorytmu służy tylko potwierdzeniu lub zaprzeczeniu, że znaleziona liczba \(\displaystyle{ z}\) faktycznie pozwala rozłożyć naszą liczbę w sposób \(\displaystyle{ 2^n-1=p_{i} \cdot (2^n-z)}\). Nie musimy weryfikować tego akurat tą procedurą, można zastosować także jakieś alternatywne metody.