[Cootje]

Temat zakładam aby nie toczyć tej dyskusji na SB...

Zaczynając od początku stworzyłem przypadkiem pewien ciekawy ciąg, który ma wiele ciekawych właściwości, a jedną z nich jest to, że liczby pierwsze układają się zawsze na indeksach o wartości kwadratu liczby 2 + 1 czyli:

dla wyrazu o indeksie [2^{0}+1] = 2
dla wyrazu o indeksie [2^{1}+1] = 3
dla wyrazu o indeksie [2^{2}+1] = 5
dla wyrazu o indeksie [2^{3}+1] = 7
dla wyrazu o indeksie [2^{4}+1] = 11
dla wyrazu o indeksie [2^{5}+1] = 13

Plik z 65536 pierwszymi wyrazami ciągu znajduje się tutaj: https://www.dropbox.com/s...erwsze.txt?dl=0

Wykres tutaj: http://i.imgur.com/hcyqCuU.jpg

Sposób generowania

Sposób w jaki generuję ciąg powstał przy próbie zrobienia czegoś na wzór gry w życie z założeniem, że komórki nie umierają i każda z nich może stworzyć następną komórkę danego typu. Na początku istnieje tylko jedna komórka o wartości 1 , która to rozpoczyna algorytm i tworzy zawsze swoją krotność. Powstałe liczby też mogą tworzyć jedynie swoją krotność z tego faktu wynika że jedynka zawsze tworzy liczby pierwsze na indeksach 2^{n}+1.

Trochę więcej o zasadach:
W pierwszym kroku mamy samotną wartość 1, która tworzy swoją krotność czyli liczbę 2 ta jest pierwsza bo powstałą z 1. W drugim kroku algorytmu posiadamy już dwie komórki, wybieramy od najstarszej do najmłodszej(Nie mylić z wartością chodzi tu o kolejność urodzenia), więc wybieramy 1, która tworzy następną swoją krotność czyli komórkę o wartości 3, a komórka z wartością 2 tworzy komórkę 4. Kolejny krok zakończony i myślę, że już widać czemu liczby pierwsze zawsze będą na pozycji 2^{n}+1 no ale lecimy dalej... W kroku trzecim 1 tworzy 5, 2 tworzy 6, 3 tworzy 9 (ponieważ 6 już istnieje i zachodzi kolizja dlatego tworzona jest następna krotność), 4 tworzy 8. I tak dalej do nieskończoności...

Przykład wizualny:
Krok1:
1 -> 2
Krok2:
1 -> 3
2 -> 4
Krok3:
1 -> 5
2 -> 6
3 -> 9
4 -> 8
Krok4:
1 -> 7
2 -> 10
3 -> 12
4 -> 16
5 -> 15
6 -> 18
9 -> 27
8 -> 24
Krok5:
1 -> 11
2 -> 14
3 -> 21
4 -> 20
5 -> 25
6 -> 30
9 -> 36
8 -> 32
7 -> 28
10 -> 40
12 -> 48
16 -> 64
15 -> 45
18 -> 54
27 -> 81
24 -> 72

Zauważcie też, że wcale nie trzeba liczyć 2^{100} dla 100 liczby pierwszej wystarczy dodać do algorytmu jakąś listę przechowującą nieużyte liczby, a zauważysz jak szybko na jej początku zbierają się same liczby pierwsze(bo to minima) pomieszane z nieprzefiltorwanymi jeszcze liczbami, a większość z nich łatwo odrzucić.

Dla 2^{5} czyli do zakresu 32 mamy już:
Znalezione i pewne liczby pierwsze:2,3,5,7,11,13
Sugerowane:13,17,19,23,26,29,31,32 (Na początku zbierają się pierwsze i dla każdego kroku są co raz to bardziej pewne i jest ich więcej na początku listy)


Jak na razie wygląda to jeszcze słabo jak zwykłe sito... ale...

Co ciekawe ciąg ten ma wiele właściwości np 2 zawsze tworzy poprzednią liczbę pierwszą mnożoną przez 2. Z początku wydaje się też, iż trzeba przeszukiwać wszystkie wygenerowane wartości aby znaleźć najmniejszą jeszcze nie wygenerowaną wartość, ale po analizie wykresów uparłem się, że można wygenerować następny krok na podstawie samych liczb z poprzedniego kroku, a nie całego zakresu. Okazało się, że faktycznie istnieje pewien schemat pozwalający policzyć dokładnie połowę liczb dla następnego kroku błyskawicznie. Uznałem, że każda komórka ma swój odpowiednik w następnym kroku(O dziwo dla komórki rodzica tworzona komórka nie musi być odpowiednikiem) , a druga połowa uzupełniająca również musi tworzyć się według określonej zasady. To nadal było mało, ale po wielu dniach na tej podstawie udało się mi opracować pewien wzór matematyczny, który nadal jest w fazie testowej.

[Fadex]

Przecież to jest sito, tylko zapisane w postaci ciągu. Zasada działania opiera się na tym, że jak liczba jest złożona to jej najmniejszy dzielnik (poza jedynką) nie będzie większy od jej pierwiastka kwadratowego... który już by był wyłapany przez jedynkę.

Meh. Nawet nie wiem po co o tym gadaliśmy.

[Cootje]

Zauważ, że jest to inne sito... Do tego jak napisałem na końcu po zdaniu "Jak na razie wygląda to jeszcze słabo jak zwykłe sito... ale... " Obecnie np jestem w stanie wygenerować krok 11 posiadając tylko liczby z kroku 10 bez poprzednich kroków.

[Fadex]

To dalej słabo, bo zmniejszasz rozmiar danych z 2^n do 2^(n-1), co dalej jest algorytmem NP - tak samo jak faktoryzacja (choć tu nie udowodniono NP-trudności). IMHO to ślepy zaułek, ale jak uważasz inaczej to możesz dowodzić że jestem w błędzie