szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 21 lut 2013, o 03:09 
Użytkownik

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

f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}
.
.
.
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 x=1. Następnie obliczamy ciągi dla liczby n:

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 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 n, struktur które wyznaczyliśmy dla ciągów zdefiniowanych w oparciu o liczby p_{1},...,p_{k}. Jeżeli któraś liczba x \in [1,n] w ciągu stworzonym w oparciu o n ma identyczną strukturę liczb parzystych i nieparzystych co x=1 w którymś z ciągów stworzonych w oparciu o liczbę p_{i}, to liczba p_{i} dzieli bez reszty liczbę n.

Przykład:

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

1. Obliczamy ciągi:

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

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

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

1,3,6,3,6,...

1,4,2,1,4,2,...

1,5,11,20,10,5,11,20,...

2. Obliczamy ciągi:

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

dla x \in [1,85].

3. Zauważamy, że ciąg 17,68,34,17,68,34,... jest identyczny pod względem struktury z ciągiem 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 5 dzieli liczbę 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 p_{i}, to jeżeli dzieli ona liczbę n, to ten ciąg musi mieć identyczną strukturę co ciąg m(\frac{n}{p_{i}}). Dlatego nie trzeba sprawdzać wszystkich ciągów m(x), dla x \in [1,n], a wystarczy ich sprawdzić dokładnie tyle, co jest liczb p_{i}. Oczywiście dokładne wyznaczanie \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 x \in [1,n], można ten ułamek jakoś szacować, przybliżać i testować tylko liczby w pobliżu \frac{n}{p_{i}}, a nie wszystkie z przedziału 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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 21 lut 2013, o 16:54 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
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.
Góra
Mężczyzna
PostNapisane: 21 lut 2013, o 18:26 
Użytkownik

Posty: 371
Lokalizacja: Wrocław
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 m(x), które generują ogromne liczby i zależą od testowanej liczby 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ę 2^n-1.
2. Bierzemy wszystkie liczby pierwsze p_{1},...,p_{k} mniejsze niż \sqrt{2^n-1} i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:

f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}
.
.
.
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 x=1, jednak tylko n elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko parzystość i nieparzystość liczb.

3. Bierzemy ciąg collatza:

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 x \in [1, 2^n-1-\sqrt{2^n-1}], jednak znów tylko 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 z o identycznej strukturze co ciąg którejś z naszych liczb pierwszych p_{i}, obliczamy 2^n-z. Następnie konstruujemy ciąg:

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

Dla x=1 o n elementach i sprawdzamy, czy ciąg ten jest identyczny pod względem struktury parzystości co ciąg collatza dla liczby 2^n-p_{i}. Jeżeli tak, to 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 2^n-1 jest liczbą pierwszą.

Przykłady:

1. Weźmy liczbę 2^4-1. Liczby pierwsze mniejsze niż pierwiastek z tej liczby, to 3.

2. 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 3,6,3,6 = n,p,n,p.

3. Obliczamy ciągi collatza dla liczb x \in [1, 11].

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

5. Obliczamy 2^4-11=5. Konstruujemy ciąg:

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: 4,2,1,4=p,p,n,p.

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

Zatem: 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:

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

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

-- 23 lutego 2013, 06:42 --

matemix napisał(a):
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 m(x), które generują ogromne liczby i zależą od testowanej liczby 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ę 2^n-1.
2. Bierzemy wszystkie liczby pierwsze p_{1},...,p_{k} mniejsze niż \sqrt{2^n-1} i konstruujemy dla tych liczb funkcje zdefiniowane rekurencyjnie:

f(x) = \left\{\begin{array}{l} \frac {3x + p_{1}}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}
.
.
.
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 x=1, jednak tylko n elementowe, więcej iteracji nie potrzebujemy, ponadto w ciągach interesuje nas tylko parzystość i nieparzystość liczb.

3. Bierzemy ciąg collatza:

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 x \in [1, 2^n-1-\sqrt{2^n-1}], jednak znów tylko 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 z o identycznej strukturze co ciąg którejś z naszych liczb pierwszych p_{i}, obliczamy 2^n-z. Następnie konstruujemy ciąg:

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

Dla x=1 o n elementach i sprawdzamy, czy ciąg ten jest identyczny pod względem struktury parzystości co ciąg collatza dla liczby 2^n-p_{i}. Jeżeli tak, to 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 2^n-1 jest liczbą pierwszą.

Przykłady:

1. Weźmy liczbę 2^4-1. Liczby pierwsze mniejsze niż pierwiastek z tej liczby, to 3.

2. 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 3,6,3,6 = n,p,n,p.

3. Obliczamy ciągi collatza dla liczb x \in [1, 11].

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

5. Obliczamy 2^4-11=5. Konstruujemy ciąg:

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: 4,2,1,4=p,p,n,p.

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

Zatem: 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:

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

Okazuje się, że dla coraz większych przedziałów liczb od 1 do 2^n coraz więcej liczb zapętla się dla ilości iteracji i<n, a dla n dążącego do nieskończoności ilość tych liczb (które zapętlają się 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 z faktycznie pozwala rozłożyć naszą liczbę w sposób 2^n-1=p_{i} \cdot (2^n-z). Nie musimy weryfikować tego akurat tą procedurą, można zastosować także jakieś alternatywne metody.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [MIX] Teoria liczb, karta z trudnymi  mol_ksiazkowy  20
 Teoria liczb - zadanie 5  krysia78  2
 Dowodu Eulera o nieskończoności liczb pierwszych  NauczycielMatematyki  8
 Zbiór liczb złożonych  Citizen  3
 NWD algorytm Euklidesa dla 3 liczb  lightinside  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl