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

[thikim 117]

jeśli liczba kończy się 9 to następna na 100% zakończy się na 3, i to nie w jakimś tam przedziale jak w artykule tylko od 0 do ever

Masz świadomość że jest to przedział nie badalny?

Równie dobrze można napisać: jakby mi 100 tonowy różowy dinozaur wyszedł z nosa to bym zauważył w tym zjawisko nie losowe.

Do tego zauważ że takich warunków "nielosowości" można wymyślać nieskończone ilości.

np. nielosowo by było jakby liczba kończyła się na 1 a następne 10 liczb w przedziale do "ever" kończyłoby się na "23"

itd.

Edytowane 19 marca 2016 przez thikim

[Jajcenty 314]

 

 

równie dobre są wszystkie algorytmy analizy technicznej na giełdzie - wspaniale tłumaczą(i nigdy się nie mylą) to co zaszło od początku notowań do teraz. ale żaden z nich nie przewidzi kursu jutrzejszego. jutro słupki analizy znowu wspaniale będą się prezentować ale dopiero jak algorytm dostanie kurs jutrzejszy...

To akurat cecha giełdy, Każdy analityk ma doskonałe wyjaśnienie dlaczego mylił się wczoraj. W konkursach  gry na giełdzie dobrze sobie radzą małe dziewczynki i małpy (losowe inwestycje).

 

 

 

Nie wiem czy słuszne jest traktowanie liczb pierwszych jako jednolitej masy. Być może dałoby się je podzielić na skończoną ilość reguł (dla niektórych są) w przyjętych skończonych przedziałach. W takim przypadku całość też byłaby (chyba) nielosowa. To taka durna hipotezka

Stanley już poruszył kwestię: jeśli ze zbioru usuniemy podzbiory wybierane według reguł czyli nielosowe, to pierwotny biały szum przestaje być biały. Ja jednak uważam, że staje się jedynie "bledszy".

[Gość Astro]

Jeśli ktoś ma ochotę na hard core, to oryginalny artykuł jest tu:

 

http://forum.kopalniawiedzy.pl/topic/25872-liczby-pierwsze-nie-s%C4%85-roz%C5%82o%C5%BCone-losowo/?do=findComment&comment=114280

 

Może dodatkowe wyzwanie? Kwadrat magiczny liczb naturalnych:

http://mathworld.wolfram.com/PrimeMagicSquare.html

Na początek może prosty 3x3 z największą możliwą sumą z naszego zakresu?

Edytowane 19 marca 2016 przez Astro

[ex nihilo 214]

 

 

Stanley już poruszył kwestię: jeśli ze zbioru usuniemy podzbiory wybierane według reguł czyli nielosowe, to pierwotny biały szum przestaje być biały. Ja jednak uważam, że staje się jedynie "bledszy".

 

Tak, N jest deterministyczne, reguły wyboru (sito) jest deterministyczne), ale "resztek" deterministycznie nie da się określić. Jedna w wielu sytuacji gdzieś na pograniczu determinizmu i losowości czy pseudolosowości. Nie tak dawno trochę bawiłem się automatami komórkowymi - niektóre reguły generują ciągi nieodróżnialne od losowych. Podobnie w niektórych przypadkach chaosu deterministycznego itd. Jest to w jakiś sposób połączone też ze sprawą odwracalności.

 

 

 

http://forum.kopalni...wo/?do=findComment&comment=114280

 

Ano Włażę tu z doskoku i niektóre rzeczy przegapiam

[Jajcenty 314]

Aktualizacja. ulong 2⁶⁴ bitów, zszedłem do 16,7 sek/pierwszą ; przerabiam 2,48 liczby/sek. Użyłem chwytu od Xitami: dzielę przez liczby 6i-1 i 6i+1. Dużo więcej z tego nie wyduszę.

Algorytm startował od 54 sek. Zeszliśmy wspólnymi siłami do 17, zatem trzykrotny wzrost szybkości.  Punkt honoru został ustalony na 10 razy, więc jeszcze trochę. Niniejszym uznaję swoje ostatnie miejsce w konkursie jednowątkowym, i poszukam szczęścia w wielu wątkach, tak by dobić do 5 sekund per liczba pierwsza.

Na pocieszenie mam, że w przeciwieństwie do mnie, primesieve.org nie potrafi pełnego ulonga. Pisownia oryginalna: Please use positive integers < 2^64 - 2^32*10

[Afordancja 57]

 

 

Punkt honoru został ustalony na 10 razy, więc jeszcze trochę.

 

To mogę podpowiedzieć (sam tego nie zrobiłem, bo trochę inaczej podszedłem do sprawy, ale ciekawi nie o ile by Ci to przyspieszyło, nie możesz przed każdym sprawdzeniem liczby zrobić jej test pierwszości, co to tam masz jakiieś wylosownae liczby (bo losować w trakcie się nie opłaca) i sprawdzasz czy któryś spełnia, jak wyjdzie, że nie jest pierwsza to olewasz ją, a jak wyjdzie, że (może) pierwsza to niestety jedziesz z koksem swoją metodą.

[Jajcenty 314]

 

 

możesz przed każdym sprawdzeniem liczby zrobić jej test pierwszości, co to tam masz jakiieś wylosownae liczby (bo losować w trakcie się nie opłaca)

Testowałem taką możliwość również. zakładałem tablice małych liczb pierwszych i względem nich sprawdzałem. To dało zejście z 48 do 27 sekund czyli całkiem sporo. Próbowałem tablice małych pierwszych o rozmiarach

od 1024 do 65355. O dziwo, rozmiar nie ma znaczenia. Powyżej 32768 miał miejsce  lekki spadek wydajności. Ostatecznie używałem tablica[8192] pierwszych pierwszych, ale po wprowadzeniu dzielenia prze 6i+1 przestały działać.

Obecnie cały zysk na szybkości to ten fragment:

 

            ulong MAX = (ulong)Math.Sqrt(Number);

            ulong dvd = 12;

 

            //divide by 6i-1 and 6i+1

 

            while (dvd <= MAX)

            {

                dvd -= 1;

                if (Number % dvd == 0)

                    return false;

 

                dvd += 2;

                if (Number % dvd == 0)

                    return false;

                dvd += 5;

            }

            return true;

[Afordancja 57]

TAk, tak ja miałem na myśli raczej:

 

https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci_Fermata

[Jajcenty 314]

 

 

TAk, tak ja miałem na myśli raczej:   https://pl.wikipedia...wszości_Fermata

Jakoś nie mam zaufania do algorytmów probabili. Próbowałem Millera-Rabina z tej implementacji: http://stackoverflow.com/questions/4236673/sample-code-for-fast-primality-testing-in-c-sharp 

Jest rewelacyjny przetwarza jakieś 2600 liczb na sekundę. Ale co z tego, jak nie daje rady powyżej 2^32

[Afordancja 57]

hm... tak przeleciałem sobie trochę większe zakresy i słabe te ich "jedynki", napisali przy kilknasu milionach było 30% (wierzę, więc naweat nie sprawdzam), sprawdziłem 54 miliony i już nie było 30% tylko 26%, dla zakresu licząć od najniższych.

 

Jak wrzuciłem prawie 100 milionów liczb pierwszych ale z górnego zakresu longa, to wyszło mi 25,0762% czyli rozłożone w miarę równo. dziwi mnie natomiast co innego. może zauważyli ale nie opisane jest to w tym artykule, albo to oczywistość i wszyscy o tym wiedzą oprócz mnie . 

Otóż:

(na pierwszy look)

niezależnie od systemu zapisu (patrzyłem na systemy od trójkowego do trzydziestojedynkowego czy jak to tam się odmienia ). rzadziej zdarzają się pary liczb pierwszych gdzie ich końcówki są takie same, a przecież nie powinno tak być.

-------------------3--------------

z:2 do:1 25970435 26,40%

z:2 do:2 23214814 23,60%

z:1 do:1 23213770 23,60%

z:1 do:2 25970436 26,40%

------------------- 98369455

-------------------4--------------

z:3 do:1 25886258 26,32%

z:3 do:3 23299262 23,69%

z:1 do:1 23297675 23,68%

z:1 do:3 25886260 26,32%

------------------- 98369455

-------------------5--------------

z:4 do:1 7000741 7,12%

z:4 do:2 6118689 6,22%

z:4 do:3 6215903 6,32%

z:3 do:1 6120037 6,22%

z:4 do:4 5257447 5,34%

z:3 do:2 6542400 6,65%

z:3 do:3 5223979 5,31%

z:3 do:4 6707867 6,82%

z:2 do:1 6214077 6,32%

z:2 do:2 5224261 5,31%

z:2 do:3 6401830 6,51%

z:1 do:1 5255235 5,34%

z:2 do:4 6752133 6,86%

z:1 do:2 6706950 6,82%

z:1 do:3 6752572 6,86%

z:1 do:4 5875334 5,97%

------------------- 98369455

 

Co więcej, nie wiem czy dobrze myślę, ale może dalo by sie to jakoś wykorzystać przy wyszukiwaniu kolejnych liczb pierwszych..

 

ale nie myślałem nad tym jeszcze zbytnio. Wrócę jeszcze do optymalizacji kodu, chcę szybciej

[edit]

I nie wiem czy nawet wraz ze wzrostem liczby podstawy systemu reprezentacji, ta zleżność sie nie pogłębia, ale już mi się nie chce teraz sprawdzać, to na jutro, (albo na nigdy jak mi przejdzie )

Edytowane 19 marca 2016 przez Afordancja

[ex nihilo 214]

(1)

2

3 5 7 - 11 13 - 17 19 - 23 - 27 29 31 - - 37 - 41 43 - 47 - - 53 - - 59 61 - - 67 - 71 73 - - 79 - 83 - - - - - - 97 - 101 103 ... inf.

 

Hmm... taki jeden mój znajomek (różnych tu mam ) po trzecim bełcie dostaje od podsklepowych kumpli kopa w kierunku domu... Na początku wektor pędu trzyma do dokładnie na deterministycznym kursie, ale stopniowo entropia wyżera mu pierwotną informację (inna interpretacja: dochodzą dodatkowe stopnie swobody, a jeszcze inna: natrafia na niejednorodności środowiska), no i wektor w te, wewte i jeszcze gdzieś zaczyna coraz bardziej nim miotać, aż w końcu (inf.) jego następny krok staje się całkowicie nieprzewidywalny, chociaż wiadomo, że im dłuższą drogę przeszedł, tym bardziej prawdopodobne jest, że jego kroki będą średnio coraz dłuższe. Czyli startując od pełnego determinizmu dochodzimy do niemal całkowitej losowości.

 

Ruszty sita pradziadka Erastostenesa są wzajemnie od siebie uzależnione w taki sposób, że ich dokładanie zwiększa nieregularności rozkładu oczek. Każda reguła określająca co przez sito może przelecieć w którymś momencie się załamuje i konieczna jest następna, bardziej skomplikowana - dążąc do nieskończoności ta reguła (lub ich suma) by musiała stawać się nieskończenie skomplikowana, chociaż oczek by było coraz mniej. Położenie ostatniego oczka (załóżmy, że takie by mogło być) byłoby całkowicie nieokreślone, poza dolną granicą (ostatnia znana l.p.). ????

 

No i to już koniec nocnych bajań napędzanych czymś takim (zamiast bełtów ):

Edytowane 20 marca 2016 przez ex nihilo

[Jajcenty 314]

  https://pl.wikipedia...wszości_Fermata

 

Nie pomaga. Erastotenes ma problem z szybkim stwierdzeniem niepodzielności. Jak na sito dostanie się duża liczba pierwsza to zostanie wykonane wszystkie SQRT(n)/2 dzieleń. W tej chwili jestem ograniczony tym, że co jakiś czas wykonuję 2^30 dzieleń, co zajmuje 15 sekund. Sito spędza 94% czasu mieląc pierwsze, 6% to odrzucanie liczb złożonych.

Edytowane 20 marca 2016 przez Jajcenty

[Fred Onizuka 8]

Z tego, co zauważyłem, to ilość liczb pierwszych w danym przedziale zmniejsza się wraz z wielkością liczb (załączony screen). W załączniku jest mój program, którym screen został wygenerowany, liczący liczby pierwsze "zwykłym" sposobem (sprawdzając podzielność od 2 do sqrt), w blokach po 1mln (większych nie miało sensu - u mnie to szło za wolno - mam 12 letni laptop    ). Są tam też statystyki: llość liczb (też w %), czas, szybkość. Pominąłem pierwszy blok (od 2 do 1mln).

liczby_pierwsze_co_1mln.zip

Edytowane 20 marca 2016 przez Fred Onizuka

[ex nihilo 214]

ilość liczb pierwszych w danym przedziale zmniejsza się wraz z wielkością liczb

 

No i się zgadza. Tak musi być, bo rusztów przybywa. Ciąg gęstości l.p. powinien dążyć do 0 w inf. Tabelka bardzo ładnie to pokazuje. Odwrotnie do tego powinna zachowywać się niepewność położenia. Od niepewności 0 ("każda następna") w przedziale 1-3 (włączam w to 1), do 1 ("cholera wie która") w inf.

 

I trochę obok - fajna ciekawostka:

https://habrahabr.ru/sandbox/68846/

Edytowane 20 marca 2016 przez ex nihilo

[Stanley 15]

Astro - wbije Ci szpile, mylisz się, zabolało?

 

Gdyby problemy intelektualne ograniczyć do kopalniawiedzy.pl to pewnie miał byś racje. W przeciwieństwie do Ciebie mam bardzo ograniczone zasoby intelektualne(dlatego co się da biorę na intuicje), nieograniczona liczbę pokus do ich marnowania. Rysuneczek się przydał - ale jako avatarek, bo matematycznie to była porażka

 

Napisałem rano niewidzialny komentarz, ale zanim poleciłem Jajcentemu OpenMP zauważyłem że zrównoleglenia natrafiają na ścianę rzeczywistości tj. problem z pamięcią cache i zapychanie magistrali pamięci ram. OpenMP jest stosunkowo łatwe i bezbolesne we wdrozeniu dla "brute force". Po najmniejszej linii oporu ->

# include <omp.h>
#pragma omp parallel for
for(x=2; x < ileśtam; x++) if (isprime(x)) printf("%d\n",x);

Wedle znalezionego kodu i testów daje przyspieszenie do 2.5x na 4 rdzeniowcu. Schody zaczynają się jeśli rozdzielić na wątki sitowanie tablicowe, mimo że wątek z wielokrotnościami 3 będzie szybszy niż 2 itd. i dzieki temu ma szanse keszować do L1,L2 swój unikalny fragment tabeli wyników. Ale wraz ze zwiększaniem liczby bazowej do dziurawienia tabeli nawet już przy wielokrotności liczby 11 (4Bx 11 > połowa linijki cache) zaczynają się poważne schody z pamięcią. Pobranie całej linijki 64bajty do cache jest na nic, skoro kolejna liczba do oznaczenia tabeli dla danego wąku będzie w kolejnej linijce pamięci i tym sposobem cały algorytm tablicowy zapycha magistrale pamięci "random" RAM. Jeśli nawet wątków jest kilka, ale wykonanie obliczeń trwa znacznie krócej niż zapisanie do pamięci to wielowątkowy algorytm można sobie wsadzić, nawet trylion rdzeni go nie przyspieszy. Pobranie wartości z L1 to ok 0.5-1ns z L2, L3 to (średnia zależna od asocjacji) na ogół kilka-naście cykli procesora, pobranie z pamięci RAM to jakieś 50-100 cykli (2Ghz) tj 30ns dla DDR3. Jeśli by zbudować tablice 2^32 i założyć że kolejne pobranie wartości trwa 33ns obliczenie trwa 33ns i zapisanie 33ns to oznaczenie wszystkich rekordów szacuje pi razy oko.. 1/2 rozmiaru + 1/3 + 1/4.. itd to razem 0.5 = zakres 2mld operacji zapisu, odczytu i obliczeń = 2mld x 100ns = 200s szok! Ojej oj.. tego nie przewidziałem

 

Jeżeli zastosować brute-force dla przedziału 4mld i uznać że dzielenie trwa 12cykli jakieś 6ns to obliczeń będzie 4mld * hm... x/2 x/3 x/4 x/5 ileś tam operacji = 24s * ileś. Dla liczby 10 sprawdzeń jest /2 /3 /4 /5 więcej nie potrzeba, dla 20 sprawdzeń jest /2 /3 /4 /5 /6.. /10 itd. więc dla 4mld będzie pół na pół = ćwierć tj. miliard sprawdzeń dla 4mld liczb? Ile wam sprawdzeń daje taki przedział? Oszacowanie mnie przerasta... 

 

Myśląc o OpenCL nie ma wyjścia musiał bym brać pod uwagę brute-force. Wyśmiewanie brute force było chyba nie na miejscu. W nich tkwi potencjał uproszczeń. Przyszło do głowy kilka pomysłów jak tablicom zaradzć, coś na kształt haszowania. ale skoro wątek wniosków i statystyk jest już opanowany przez konkurencje a OpenMP zapewni Jajcentemu 5s bez wielkiego wysiłku, po co się trudzić 

 

PS  http://www.paranormalne.pl/tutorials/article/496-skrywany-przez-nature-kod-liczb-pierwszych/

Edytowane 20 marca 2016 przez Stanley

[ex nihilo 214]

 

 

PS http://www.paranorma...czb-pierwszych/

 

Cytat: "odnalezienie wzoru liczb pierwszych jest jedną z największych zagadek matematycznych."

 

Uważam, że taki wzór - skończony, przyjmując, że jednoznaczny ciąg zbieżny też jest "skończony" - nie istnieje.

 

Być może - gdyby znane były wszystkie liczby pierwsze, a to nie jest możliwe - taki wzór by można stworzyć "wstecznie". Ciąg wzrastania niepewności położenia l.p. jest rozbieżny do nieskończoności. To jak rozbite jajko (spadam zrobić jajecznicę)

[Stanley 15]

Na matematyka.pl znalazłem sugestie uproszczeń:

http://www.matematyka.pl/2296.htm

Brute force: przygotowana wcześniej tabela sqrt() Jajcenty?

Zgaduje że chodzi o: uznanie że sqrt() dla 64...65...i dla 80 = 8 (bo dla 81 = 9) to potrzeba mniej wywołań funkcji sqrt niż gdyby liczyć dla kolejnej liczby. W związku z tym należy zbudować tabele adresowaną z pominięciem kilku bitów a więc np. 512MB dla 2^32 możliwe że będzie szybsza niż wywoływanie funkcji 16x sqrt? Wróć.. bez budowania.. już widzę że sqrt(x) dla x+2*sqrt(x) jest floor() takie samo? Więc dla kolejnych testowanych liczb wystarczy zapamiętać dwie zmienne static int sqrtx i wartość static int sqrt_rekalkuluj; if (x > sqrt_rekalkuluj) { sqrtx = sqrt(x); sqrt_rekalkuluj = x + 2*sqrtx; } itd....  Ale to pewnie złe bo całkowicie samodzielnie wymyśliłem

Sito: użycie bita zamiast całego bajta dla tabeli, co daje 512MB dla 2^32 i zakres 512 kolejnych liczb dla linijki cache.

 

Większość znalezisk w necie(w tym rzecz jasna stackoverflow) to rozmaite mutacje Atkina, Erastotenesa a jest jedno nowum które nie zostało wymienione:

Algorytm Shora ale dla komputera kwantowego - realne zagrożenie dla RSA

https://pl.wikipedia.org/wiki/Algorytm_faktoryzacji_Shora

 

Samodzielnie po głowie kołacze sie analizowanie liczb w systemie dwójkowym - test bitów, zliczanie bitów itp. i hasło pt. CRC które w jakimś tam stopniu jest związane z liczbą pierwszą i dzieleniem a zostało sprytnie zoptymalizowane do tabelek pomocniczych, przesunięć i xorowania. (w sumie to dzielenia pod kreską jak na lekcji matematyki) Wiele bithacków doczekało się przeniesienia w SSE, AVX https://graphics.stanford.edu/~seander/bithacks.html

 

Więc może by dało się wymyślić tablicową "uniwersalną regułę" dla 256 liczb. Łącząc bajt z bajtem w formie czegoś na kształ konstrucji sumatora z przeniesieniem i pożyczką masowo eliminować wiele testów. Dzwoni w kościele ale nie wiem po co. Pewnie algorytm Atkina jest takim czymś.. matematycznie wyliczonym optymalnym "polynominal" dziesiętnym. Przyznaje nie czaje, wkleiłem bo mądrze wyglądało

Edytowane 20 marca 2016 przez Stanley

[Afordancja 57]

 

 

Więc może by dało się wymyślić tablicową "uniwersalną regułę" dla 256 liczb. Łącząc bajt z bajtem w formie czegoś na kształ konstrucji sumatora z przeniesieniem i pożyczką masowo eliminować wiele testów. Dzwoni w kościele ale nie wiem po co.

 

Na tym polega mniej więcej mój "big update" który pewnie zrealizuję jutro, bo dziś niestety prognozuję, że dzieci nie będą w nocy spać (chore) więc i ja dlatego idę spać

na ten moment jadę z prędkością 

250 tysięcy liczb pierwszych na sekundę, albo 1,7 mln. na sek. w zależności z której strony zakresu jadę, ale czuję, że da się dzieki właśnie dzięki hm... włąsnie doszedłem do wniosku, że nie wiem czy mówimy o tym samym

Mógłbyś opisać szerzej. ?

[Stanley 15]

czuję, że da się dzieki właśnie dzięki hm... włąsnie doszedłem do wniosku, że nie wiem czy mówimy o tym samym

 

Myśle że obserwujesz zjawisko związane "jedynie" z cache association, pobaniami wyprzedzającymi itp.

Mozliwe że po to mi dzwoni bitami w głowie po nic więcej.

Edytowane 20 marca 2016 przez Stanley

[ex nihilo 214]

Taka zabawka w łeb mi wlazła:

0,12357111317192327293137414347535961677173798397101103...

Pewnie nie jestem pierwszy, ale nie znalazłem w sieci. Może dlatego nie znalazłem, że nadaje się to tylko do drukowania na rolkach wiadomego papieru... chociaż własności tej liczby powinny być dosyć ciekawe. Np. powinna przejść wszystkie testy losowości

Jeśli komuś skojarzy się z tym:

0,12345678910111213141516… (https://en.wikipedia.org/wiki/Champernowne_constant)

to skojarzy się dobrze. Zasada konstrukcji jest podobna, tyle że zamiast kolejnych naturalnych użyte zostały kolejne pierwsze.

Ciekawe byłoby porównanie stopnia losowości obu. Przypuszczam, że ta moja zda testy lepiej.

 

I jeszcze jedno dziwadło:

0,0011313133115313551531531331...

Jak zostało zrobione?

Kto pierwszy poda odpowiedź, zarobi plusa

Edytowane 22 marca 2016 przez ex nihilo

[Weinreb 0]

Dzień dobry,

 

nie znam się na matmie, ani programowaniu ale kiedyś ktoś mi pokazał, że można zrobić właśnie coś takiego z liczbami pierwszymi by poprzez pewne operacje "+ " i "-" dały liczbę 0, a podstawiało się do liczby PI w taki sposób, że na dole ciągu liczb układano liczby pierwsze zaczynające się od liczb parzystych u góry zamieszczano liczby kończące się na nieparzyste i jeszcze wyżej układano liczby z zerem i piątką w środku lub na początku liczby pierwszej, no i nie mogły się powtarzać. Spróbowałem coś takiego rozpisać na kartce

 

                               151  157

    11   31   19             13           29     59 23       43                                   53 73      83

3. 1 4  1  5 9   2  6   5 3  5    8   9   7  9   3   2    3  8   4   6   2    6      4    3   3  8    3

       41                61              83                    211    89 47 67 223 601 401         809

 

o ile dobrze to jest rozpisane to dla nieparzystych wyszły dwie opcje:

11+31+19-13-29-59-23+43-53+73 = 0

11+31-19-13-29+59+23-43+53-73 = 0

 

a dla zaczynających się parzyście:

41-61-83-211-89+47-67+223+601-401 = 0

 

jak widać dla dziesięciu liczb pierwszych, ciekawe ile jest takich dziesiątek, i czy w ogóle to ma jakiś sens...?

 

 

:

 

 

. 

[Stanley 15]

http://www.algorytm.edu.pl/images/prim100000.txt

Próbowałem ogarnąć umysłem, patrząc na powtarzalność cyfr  i grup cyfr na kolejnych miejscach dziesiętnych ze szczególną uwagą dla końcówek pierwszych wcześniej widzianych jak 1,3,5,7,11,13...31,37, 57 itd.. im dalej w las miejsca dziesiętnego tym więcej normalnie kolejnych 1,2,3,4,5,6... na najbardziej znaczących pozycjach. Niektóre końcówki pierwsze wręcz znikają pojawiają się niepierwsze końcówki np. 99 w liczbie 19299,

Może przydały by się wykresy 2D x,y przyrostów występowania w końcówce cyfr 1,2,3,4,5,6,7,8 itd. na drugim miejscu od prawej, na trzecim itd.. Ale wyobrażam sobie że na kolejnych miejscach dziesiętnych różnice między częstotliwością występowania będą się zacierać. Np. dwójka początkowo rzadko występuje 1,2,3,5,7,11,17,19,21,23,31,37 itd ale prawdopodobieństwo że w liczbie pierwszej 5 cyfrowej najbardziej znacząca albo druga z koleji jest 0 lub 1 lub 2 lub 3 itd. będzie równomiernie bliskie 1/10..

 

Ślepa uliczka, zwyczajnie widać wplatanie coraz większej liczby zależności którym nie sposób zadać stałe przedziały, stałą częstotliwość. Wiec zajrzałem na stronie w ciąg Fibonaciego - skoro wizualizacje graficzne przypominają spiralę, próbując jakoś udziwnić "wpleść w niego" liczby pierwsze, stworzyć ciąg bliźniaczy sumując kolejne liczby fibonaciego w odstępach 1,2,3,5,7.. ale oczywiście bez sensu. Za to znalazłem ciekawostki mając na myśli algorytm i program: liczenie pierwiastka, konwersje systemów, rozkład liczby

http://www.algorytm.edu.pl/algorytmy-maturalne/newton-raphson.html

http://www.algorytm.edu.pl/algorytmy-maturalne/rozklad-na-czynniki.html

http://www.algorytm.edu.pl/algorytmy-maturalne/pozycyjne-reprezentacje-liczb.html

 

"Liczby złożone będą miały co najmniej dwa czynniki pierwsze. Liczby pierwsze się nie rozkładają". Jeśli się nie rozkładają to wygląda że nie trzeba dzielić przez 1,2,3,4,5,6,7,8,9... sqrt(x) ale rozkładać na czynniki pierwsze dzieląc wyłacznie przez kolejne liczby pierwsze znalezione wcześniej, a ponieważ libcz pierwszych w zakresie od 0 do sqrt(x) jest ich mniej niż liczb naturalnych 0,1,2,3,4,5,6... to może znacznie przyspieszyć obliczenia?

Dobrze kombinuje?

Edytowane 24 marca 2016 przez Stanley

[Jajcenty 314]

ponieważ libcz pierwszych w zakresie od 0 do sqrt(x) jest ich mniej niż liczb naturalnych 0,1,2,3,4,5,6... to może znacznie przyspieszyć obliczenia? Dobrze kombinuje?

Dobrze kombinujesz. Szacuję że dzieleń będzie niecały rząd mniej (2x10⁸  vs 10⁹) niż w przypadku "normalnego" sita Eratostenesa. 

Niestety wymogi pamięciowe duże. Dla rozkładania Int64 Potrzeba jakieś 4 GB na stercie żeby zapamiętać 1.94x10⁸ liczb pierwszych,

na szczęście w postaci Int32. (liczb pierwszych poniżej 2³² powinno być 2³²/ln(2³²))  A gdybyśmy tak chcieli rozłożyć 2¹²⁸ to już duuuuża sterta jest potrzebna.

Edytowane 24 marca 2016 przez Jajcenty

[Stanley 15]

Sito liniowe i inne matematyczne algorytmy z wyjaśnieniami gotową implementecją w Lazarusie, Free Basic i Code::Blocks http://eduinf.waw.pl/inf/alg/001_search/0012.php

Kod można wkleić tu: http://cpp.sh/

http://www.quitebasic.com/

[Afordancja 57]

A słyszeliście może gdzieś jakieś porównanie jeśli chodzi o szybkość algorytmów na testy pierwszości? 

( Dla wielkich liczb,(naprawdę wielkich) )

 

Próbowałem zrobić test Millera-Rabina, pewnej liczby (no dobra podam ją "miała powyżej 100 milionów zer   , czytaj chciałem zagrać w "totolotka" i obstawiłem, że ta będzie pierwsza, i jak będzie to zgarniam 100 tys. usd ) i po dobie musiałem niestety przerwać bo potrzebowałem użyć kompa a pamieć mi prawie całą z żarło.

Nawet nie wiem jakiego rzędu czasu mam się spodziewać, (hm...zrobię testy na mniejszych liczbach) do tygodnia, jestem w stanie czekać. (tylko test jednej liczby w tydzień to słabo, bo wytypowałem ich więcej)