Liczby pierwsze nie są rozłożone losowo?

[Matcher 2]

Czyli ostatnie 5 które nie mają dzielników z "210":

 

210n+191 -

210n+193 -

210n+197 -

210n+199 -

210n+203 = 7(30+29) +

210n+209

 

A jeśli przyjmę,że liczba y podzieli się na 11( lecz wtedy 210 się nie dzieli) to liczb faktycznie naliczę 43

 

Teraz dorzucę małą cegiełkę do "210"

 

Wykorzystując wzór 210n + 161 dla n dążącego do nieskończoności uzyskamy zawsze liczbę podzielną przez 7.(chyba)

 

Przykładowo 210x22 + 161 = 4781 /7 = 683 

 

W okresie "30" najmniejsza taka liczba ma numer 41 i jest równa 161 !!. Potem nr 41 zwiększamy cyklem zawsze o 56 = 97 (371) 97 + 56 = 153(581)

 

W celu sprawdzenia czy Liczba o numerze np. 6089  z okresu "30" jest podzielna przez 7 to odejmujemy od niej 41 i dzielimy przez 7. Jeśli reszta z dzielenia = 0 to liczba jest podzielna przez 7.

 

Wzór 30x+y generuje kandydatki na liczby pierwsze. Pierwsza kandydatka odrzucona będzie dla x=5 i y = 11 Druga kandydatka odrzucona dla x=12 y=11

Y jest stałe, a X zwiększa się zawsze o 7.

 

Ciekawe jak działa to w "210" Kolejne zamknięte drzwi przede mną..

[Gość Astro]

 

 

Wykorzystując wzór 210n + 161 dla n dążącego do nieskończoności uzyskamy zawsze liczbę podzielną przez 7.(chyba)

 

Zawsze, bo 210n+161 = 7(30n+23)

[Matcher 2]

Teraz to: 210n+161 = 7(30n+23) tworzy nowy warunek i Unowocześnia "30".  Ja chyba tego szukałem już dawno temu

 

Teraz muszę poprawić algorytm i sprawdzić o ile więcej wygeneruje liczb niż algorytm generujący 100% LP.

 

A jeszcze trzeba się zabrać za "2310".

[Gość Astro]

 

 

Teraz muszę poprawić algorytm i sprawdzić o ile więcej wygeneruje liczb niż algorytm generujący 100% LP.

 

110% liczb pierwszych? Niestety, ja już tak nie potrafię.

[Matcher 2]

100% LP , ale to zajmuje trochę czasu.

 

Wzorem ulepszonym  30x+y na 1 000 000 liczb wygenerowało się teraz 982 143 liczb, czyli mniej o 17857.

 

Liczby podzielne przez 7 zostały odrzucone. Pytanie jest takie czy odrzuciło wszystkie?

[Gość Astro]

Przestaję nieco rozumieć. Możesz podesłać swój kod? Chłopcy zapewne się obudzą i chętnie podyskutują.

[Matcher 2]

Kod programu, który tylko generuje zbiór liczb ze wzoru 30x+y. Dodatkowo odrzuca liczbę o nr. 41 i wyższe co 56 pozycji. Chcę to teraz tak zmodyfikować,by mi generował 100% LP , ale muszę dołożyć dzielenie.

pime.txt

[Gość Astro]

Faktycznie, do generowania kolejnych liczb pierwszych jeszcze daleko.

 

 

 

idę w małą hipotezę, że da się zejść do 43

 

Niestety, hipotezę trzeba porzucić na rzecz małego twierdzenia, że niezależnie od wyboru a w przedziale <a,209+a> ZAWSZE mamy 48 liczb do sprawdzenia, bo zawsze jest 48 liczb, które nie dzielą się przez 2,3,5 lub 7. Łatwo to sprawdzić (dla zwolenników kodów ) linijką typu

   if (n%2 && n%3 && n%5 && n%7) count++;

Podobnie w przypadku cyklu 2310 (2*3*5*7*11) zawsze mamy 480 liczb do sprawdzenia. Jak widać, dłuższe cykle są coraz wydajniejsze, choć nie tak jak optymistycznie zakładałem wcześniej (w rzeczywistości ok. 27%, 23%, 21%, …).

Dla dowolnego cyklu 30 zawsze mamy 8 liczb do sprawdzenia; przykładowo prościej zapisać odpowiednie ciągi jako:

30n+1, 30n+7, 30n+11, 30n+13, 30n+17, 30n+19, 30n+23 oraz 30n+29.

 

Kluczem w zabawie jest to, że y i długość cyklu są względnie pierwsze, ale na razie nie potrafię udowodnić sobie na kartce stałości 48 niezależnie od wyboru a, jak również nie wiem, jak wyliczyć sobie odpowiednią ilość liczb do sprawdzania w zadanym przedziale:

      6 (2*3):                2

    30 (2*3*5):             8

  210 (2*3*5*7):        48

2310 (2*3*5*7*11):  480

Jeśli na sali jest jakiś matematyk, to proszę o pomoc.

Ed. Przy cyklu 30030 (2*3*5*7*11*13) mamy do sprawdzenia 5760 liczb (ok. 19%), a przy 510510 (…*13*17) – 92160 (18%).

Coś chyba jest na rzeczy: 2*(5-1)=8; 8*(7-1)=48, 48*(11-1)=480, 480*(13-1)=5760, 5760*(17-1)=92160…

[Matcher 2]

A jeśli weźmiesz stały zakres <0,210> i potraktujesz go cyklem "210" to otrzymasz 48 kandydatek. Sprawdź czy traktując ten sam zakres cyklem "2310" uzyskasz w tym samym zakresie mniej kandydatek (obstawiam, że zostanie 43). Jeśli tak to zwiększ cykl i znowu sprawdź. Wydaje mi się ,że im większy cykl tym więcej liczb wyrzucisz z podanego zakresu. Ilość liczb będzie spadać,aż ustabilizuje się stałym poziomie. Jeśli dobrze rozumiem to takim postępowaniem można zrobić samonapędzającą się "maszynę" liczb pierwszych 100-procentowych

[Gość Astro]

 

 

Sprawdź czy traktując ten sam zakres cyklem "2310" uzyskasz w tym samym zakresie mniej kandydatek

 

Przeczytaj to co napisałem wyżej ze zrozumieniem, a znajdziesz odpowiedź.

[Matcher 2]

Ok rozumiem

 

Teraz pytanie: Czy dany cykl tworzymy tylko z liczb pierwszych (11,13,17....43) "13082761331670030" I teraz czy dalej mnożymy przez 49 czy ją omijamy?

[pogo 102]

 

 

Jeśli dobrze rozumiem to takim postępowaniem można zrobić samonapędzającą się "maszynę" liczb pierwszych 100-procentowych

Plan genialny. Potrzebujemy tylko komputera o nieskończonej pamięci RAM

[thikim 117]

No ja bym tu nie był takim optymistą. Zysk rośnie coraz wolniej.

 

 

Faktycznie, do generowania kolejnych liczb pierwszych jeszcze daleko

Zależy jakie liczby chcemy generować. Im większe tym dalej

Nie chce mi się wszystkiego czytać. Macie jakiś nowy lepszy ciąg do sprawdzenia dla 100 mln liczb pierwszych?

Edytowane 2 listopada 2016 przez thikim

[Gość Astro]

 

 

Potrzebujemy tylko komputera o nieskończonej pamięci RAM

 

Musiałaby mieć też "odpowiedni" czas dostępu, by "odpowiedniej" szybkości procesora nie wspomnieć.

 

 

 

No ja bym tu nie był takim optymistą. Zysk rośnie coraz wolniej.

 

Szybciej się nie da.

 

 

 

Zależy jakie liczby chcemy generować. Im większe tym dalej

 

Niestety, ale niezależnie od wyboru cyklu, przykładowo 210, granica

  π(n+210)-π(n)

przy n dążącym do nieskończoności wynosi 0.

 

 

 

Macie jakiś nowy lepszy ciąg do sprawdzenia dla 100 mln liczb pierwszych?

 

Podam NAJLEPSZY: p_i, gdzie p_i to i-ta liczba pierwsza. Poniżej połowa sukcesu.

https://primes.utm.edu/lists/small/millions/

[thikim 117]

Tego ciągu nie podejmę się sprawdzać

[Gość Astro]

No to jak chcesz dojechać do 100 mln?

[thikim 117]

Sprawdzając ciąg klasyczny, czyli liczby nieparzyste, co już zrobiłem.

p_i, gdzie p_i to i-ta liczba nieparzysta.

Oraz sprawdzając każdy inny ciąg z większą gęstością liczb pierwszych, jak tu zaproponowane.

Z wyjątkiem tego ciągu liczb pierwszych o którym piszesz. Tego sprawdzać nie będę

Edytowane 3 listopada 2016 przez thikim

[Gość Astro]

 

 

Sprawdzając ciąg klasyczny, czyli liczby nieparzyste, co już zrobiłem.

 

Faktycznie, do zabicia komara chyba nie można użyć większego kalibru (bo nie istnieje ).

 

 

 

Oraz sprawdzając każdy inny ciąg z większą gęstością liczb pierwszych, jak tu zaproponowane.

 

Podeślij może jakiś kod, bo na forum robi się nudnie.

[Matcher 2]

Widzę,że od mojej ostatniej wizyty tutaj niewiele się zmieniło

 

Ehh nie mam kiedy zająć się dalej tym tematem. Trzeba zbadać sprawę powtarzających się liczb podzielnych przez 7. Co 56 liczba będzie skreślona z sita opisanego wzorem 30x+y... hmn stwierdzam,że będzie można wykreślić więcej takich liczb Coś w tym musi być..

[Gość Astro]

 

 

Widzę,że od mojej ostatniej wizyty tutaj niewiele się zmieniło

 

Owszem. Jeśli jesteś WIELKI, to ZAPODAJ. KW zapali pod kotłami i machina ruszy.

[Matcher 2]

Tak przypuszczałem,że wzór 210n+161 to tylko wierzchołek góry lodowej

 

Chciałem teraz pójść w trochę inną stronę.. tzn w kierunku liczb podzielnych przez 7. Powyższy wzór bardzo ładnie wskazuje nam ,które liczby są podzielne przez 7, bez jakiegokolwiek sprawdzania(dzielenia przez 7) każdej liczby. Jednocześnie ten wzór łączy się ze wzorem 30x+y opisującym zbiór liczb, z których można powykreślać te podzielne przez 7.

 

W zbiorze 30x+y najmniejsza liczba podzielna przez 7 to 49 i ma ona indeks #12 . Teraz można posłużyć się "przesunięciami" czyli co dodać do tego indeksu ,by następna liczba również była podzielna przez 7. Czyli do #12 dodajemy teraz 7 i mamy #19 = 77,  Następnie:

 

#19 + 4 = #23 = 91

#23 + 7 = #30 = 119

#30 + 4 = #34 = 133

#34 + 7 = #41 = 161

#41 + 12 = #53 = 203

#53 + 3 = #56 = 217

#56 + 12 = #68 = 259

#68 + 7 = #75 = 287

 

Cykl dodawania (7-4-7-4-7-12-3-12)cały czas się powtarza i generuje liczby podzielne przez 7.

To samo można zrobić na liczbach nie-indeksowanych... Najmniejsza to 49:

 

49 + 28 = 77

77 + 14 = 91

91 + 28 = 119

119 + 14 = 133

133 + 28 = 161

161 + 42 = 203

203 + 14 = 217

217 + 42 = 259

259 + 28 = 287

 

Tutaj powtarzamy cykl (28-14-28-14-28-42-14-42)

 

Ciekawe jest to ,że liczby te pojawiają się w zbiorze 30x+y, a dzięki wyliczeniom 210n+161 można było dowiedzieć się, gdzie się dokładnie znajdują. Teraz wystarczy sprawdzić o ile więcej dzięki tej metodzie powyrzucamy liczb i jak bardzo zbliżymy się do wyznaczania dokładnych Liczb Pierwszych

[pogo 102]

@@Matcher,

Widzę, że nie przeczytałeś wcześniejszych postów...

 

Cóż. Proponuję abyś dał przykład zastosowania Twojej metody do znalezienie najmniejszej liczby pierwszej większej od 10 000 000. 

[thikim 117]

Podeślij może jakiś kod, bo na forum robi się nudnie.

int iloscliczbpierwszych = 100000000;

            int[] tablicaliczbpierwszych = new int[iloscliczbpierwszych];
            int[] tablicageneracyjna ={11,13,17,19,23,29,31,37};
            tablicaliczbpierwszych[0] = 7;
            tablicaliczbpierwszych[1] = 11;

            int licznikliczb = 1;
            int pierwiastekliczby;
            int liczba = 11;

            for ( int licznikglowny = 0; licznikliczb < iloscliczbpierwszych; licznikglowny ++)
            {
                for (int licznikpomocniczy = 0; licznikpomocniczy < 8; licznikpomocniczy++)
                {
                    liczba = licznikglowny * 30 + tablicageneracyjna[licznikpomocniczy];
                    bool czypodzielna = false;
                    pierwiastekliczby = (int)Math.Sqrt(liczba);
                    for (int licznik = 0; pierwiastekliczby >= tablicaliczbpierwszych[licznik]; licznik++)
                    {
                        if (liczba % tablicaliczbpierwszych[licznik] == 0)
                        {
                            czypodzielna = true;
                            break;
                        }
                    }
                    if (!czypodzielna)
                    {
                        tablicaliczbpierwszych[licznikliczb] = liczba;
                        licznikliczb++;
                    }

                }
            }

Dodałem po prostu tablicę z tymi liczbami z ciągu do generowania liczb pierwszych. I musiałem dodać pętlę for żeby z tej tablicy generować liczby pierwsze.

Zasadniczo może coś można delikatnie uprościć ale sama idea opisu tego dla tych sposobów wydaje się słuszna. Ogólnie robi się tablicę, ogólnie robi się dodatkową pętla for. Łatwo można to dalej już skalować dla różnych ciągów w tablicy.

Być może szybsze byłoby wymienienie kolejno poszczególnych liczb i powtórzenie dla każdej z nich (jest ich 8) sprawdzenia.

Objętościowo by to wzrosło ale szybkościowo mogłoby być lepsze (obyło by się wtedy bez tablicy i dodatkowej pętli). Może kiedyś sprawdzę.

Edytowane 5 grudnia 2016 przez thikim

[Matcher 2]

Czyli tym algorytmem tworzysz liczby ze zbioru 30x+y. Sugerowałem, by zaczynając od liczby 41-wszej (161) eliminując ją i pomijać następne co 56 liczb.

 

W zakresie 11-1 000 000 używając (30x+y) masz takich liczb  266 669. Eliminując co 56 liczbę otrzymasz już tych liczb o 4760 mniej.

 

Teraz wystarczy zaczynając od 49 eliminować liczby dodając (28+14+28+14+28+42+14+42).

[Gość Astro]

 

 

Powyższy wzór bardzo ładnie wskazuje nam ,które liczby są podzielne przez 7,

 

 

najmniejsza liczba podzielna przez 7 to 49 i ma ona indeks #12 . Teraz można posłużyć się "przesunięciami" czyli co dodać do tego indeksu ,by następna liczba również była podzielna przez 7. Czyli do #12 dodajemy teraz 7 i mamy #19 = 77

 

Fajnie, ale po co to cudo? Zgubiłeś nieco po 49, a przed 77.

Jeżeli chodzi Ci o jakiś ciąg liczb podzielnych przez 7, to polecam bardzo ładnie wyglądający:

a_n = 7*10ⁿ + 7

Podzielność przez 7 nie jest aż tak bardzo skomplikowaną cechą:

http://www.math.edu.pl/cechy