NukeBoards - Kreatywność przede wszystkim
FAQFAQ  SzukajSzukaj  UżytkownicyUżytkownicy  DownloadDownload
RejestracjaRejestracja  ZalogujZaloguj

Odpowiedz do tematu
Poprzedni temat :: Następny temat
Liczby pierwsze
Autor Wiadomość
Cootje 
Legenda


Posty: 639

Prestiż
Wysłany: 28-01-2016, 22:18   Liczby pierwsze

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.
_________________
Mój klucz publiczny PGP
 
     
Fadex 
Legenda
#4; #12; #18; #20; #21; #27


Pojedynki: nie
Steam:
Posty: 1773

Prestiż
Wysłany: 28-01-2016, 23:51   

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.
_________________
If it doesn't have to work, I can optimize any code to a runtime of zero. What's your superpower?
wat
 
 
     
Cootje 
Legenda


Posty: 639

Prestiż
Wysłany: 29-01-2016, 00:02   

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.
_________________
Mój klucz publiczny PGP
 
     
Fadex 
Legenda
#4; #12; #18; #20; #21; #27


Pojedynki: nie
Steam:
Posty: 1773

Prestiż
Wysłany: 29-01-2016, 00:08   

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 :P
_________________
If it doesn't have to work, I can optimize any code to a runtime of zero. What's your superpower?
wat
 
 
     
Wyświetl posty z ostatnich:   
Odpowiedz do tematu
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Nie możesz załączać plików na tym forum
Możesz ściągać załączniki na tym forum
Dodaj temat do Ulubionych
Wersja do druku

Skocz do:  

PSK Cytaty Klikibaza - kopia wszystkich klików Klikipedia - encyklopedia o tworzeniu gier Discord KlikCzat Zaproszenie
Daj piniondza Wielkie Muzeum Klikowe

Powered by phpBB modified by Przemo © 2003 phpBB Group