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.
Nowy algorytm znajdowania liczb pierwszych
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Nowy algorytm znajdowania liczb pierwszych
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.
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Nowy algorytm znajdowania liczb pierwszych
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 --
-- 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 --
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.matemix pisze: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.