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

[KopalniaWiedzy.pl 318]

Matematycy z Uniwersytetu Stanforda, Robert Lemke Olivier i Kannan Soundararajan, odkryli, że rozkład ostatnich cyfr w liczbach pierwszych nie jest tak losowy, jak się dotychczas wydawało. A to sugeruje, że same liczby pierwsze nie są rozłożone losowo.

Jak pamiętamy, liczby pierwsze są to liczby naturalne większe od 1, dla których istnieją tylko dwa dzielniki - 1 i one same. Definicja tych liczb jest prosta, jednak naukowcy wciąż do końca ich nie rozumieją. Nie potrafią, na przykład, ich przewidzieć, a znalezienie każdej kolejnej jest coraz trudniejsze. Dotychczas sądzono, że liczby pierwsze są rozłożone całkowicie przypadkowo. Wiadomo, że liczby pierwsze (z wyjątkiem 2 i 5) kończą się na 1, 3, 7 lub 9. Przy losowym rozłożeniu oznacza to, ni mniej ni więcej, że po liczbie zakończonej na 1 (np. 11) istnieje 25% szans, że kolejna liczba pierwsza również będzie zakończona na 1. Okazuje się jednak, że to nieprawda.

Olivier i Soundararajan przeanalizowali liczby pierwsze do wartości kilkunastu biliardów i dokonali kilku interesujących obserwacji. Okazało się, na przykład, że do pierwszych kilkunastu milionów dla liczby pierwszej zakończonej na 1 kolejna liczba pierwsza zakończona na 1 pojawiała się w 18,5% przypadków. Gdy liczba pierwsza kończyła się na 3 lub 7 to kolejna pierwsza była zakończona na 1 w 30% przypadków, a gdy pierwsza kończyła się na 9, to kolejna pierwsza w 22% przypadków kończyła się na 1. Taki rozkład sugeruje, że ostatnie cyfry liczb pierwszych nie występują losowo, co wskazuje, że liczby pierwsze nie są losowe. Z drugiej jednak strony naukowcy odkryli, że im bardziej zwiększa się odległość pomiędzy kolejnymi liczbami pierwszymi, tym bardziej losowy jest rozkład ich ostatnich cyfr.

Naukowcy nie wiedzą, skąd wynika ten brak losowości. Przypuszczają, że ma to związek z hipotezą k-krotek. Niestety, hipoteza ta wciąż nie została udowodniona.

« powrót do artykułu

[Afordancja 57]

(żart)

A ja mam inny dowód, że te liczby nie są losowe. Jeżeli je zapiszemy w systemie dwójkowym, to jeżeli ostatnia cyfra danej liczby pierwszej kończy się na 1, to kolejna w 100% przypadków, również kończy się na 1. ta da!

 

hm..nie spróbowali innych statystyk dla innych systemów zapisu, może by coś z tego wykoncypowali. 

ps.

"Zaraz" sam poszukam tych liczb (jeżeli jest jakaś oficjalna lista) i przeprowadzę badania, gdzie to potem ogłosić?

[thikim 117]

Zaraz, zaraz, a dla pierwszych 100 to prawdopodobieństwo także dla "1" wynosi 18,5%?

[Jajcenty 314]

Naukowcy nie wiedzą, skąd wynika ten brak losowości. Przypuszczają, że ma to związek z hipotezą k-krotek. Niestety, hipoteza ta wciąż nie została udowodniona.

No fizyk nazwałby to silnym potwierdzeniem - obie hipotezy wzajemnie się wspierają. Niestety o ile pamiętam, matematycy mają głęboką niechęć do dowodów numerycznych. W tym przypadku może się okazać, że efekt braku losowości zmienia się co każde 10¹⁰⁰ by efekcie być całkowicie losowym jeśli tylko przedział jest szerszy niż 10²⁰⁰

Te kilkanaście biliardów czyli 10¹⁵ to coś dziwnego. Mój laptop bez łaski obsługuje liczby całkowite do 9x10¹⁸. Mogli przebadać przedział znacznie szerszy.

Zaraz się z Afordancją za to weźmiemy

edit: nawet nie wiedziałem: mam tu ulong! Moge se turlać numerki do 1,8x10¹⁹. Ha!

 

ulong.MaxValue = 18 446 744 073 709 551 615

Edytowane 16 marca 2016 przez Jajcenty

[Uriziel 0]

Nie rozumiem dlaczego wyniki podane są w formie 

 

 

pierwszych kilkunastu milionów

przecież dosłownie w kilku liniach kodu byłem w stanie sprawdzić że ta zależność jest praktycznie taka sama w dalszym zakresie liczb pierwszych:

(jako bonus sprawdziłem też zależność przy ostatniej cyfrze innej od 1 i wyniki są równie ciekawe)

Dla liczb pierwszych POWYŻEJ 15 000 000 (do 32452843)
1 => 17.66%
3 => 30.44%
7 => 31.18%
9 => 20.72%

Dla liczb pierwszych PONIŻEJ 15 000 000 (do 32452843)
1 => 17.13%
3 => 31%
7 => 31.84%
9 => 20.03%

Rozrzut wartości jest największy dla ostatniej cyfry równej 9 (cały zakres do 32452843):

1 => 33.5%
3 => 25.65%
7 => 23.47%
9 => 17.38%

Przy dostępnej dla nich mocy obliczeniowej powinni sprawdzić to dla przynajmniej 50 000 000 liczb pierwszych.

[Gość Astro]

gdzie to potem ogłosić?

Zaraz się z Afordancją za to weźmiemy

 

Chłopaki. Trzymam kciuki!

Zanim jednak się weźmiecie za robotę, to pewnie trzeba zassać bibliotekę (stosowali ją autorzy publikacji):

http://primesieve.org/

Problem skalowania daje jednak do myślenia. Samo sito (skoro analizujemy "all primes") nie jest chyba problemem, choć na ulong proponuję jednak urlop. Polecam też zacząć od przestudiowania oryginalnej publikacji:

http://arxiv.org/pdf/1603.03720v2.pdf

 

W tym przypadku może się okazać, że efekt braku losowości zmienia się co każde 10¹⁰⁰

 

Pełna zgoda. Mówi to nawet fizyk.

 

nawet nie wiedziałem: mam tu ulong!

 

Jakoś nie śmiałbym wątpić, że masz long. Jaki problem z zastosowaniem "unsigned", czyli olaniu bitu znaku? Może jestem stary, ale było to już w KR C…

 

Nie rozumiem dlaczego wyniki podane są w formie

pierwszych kilkunastu milionów

 

 

bo to tak "dla przykładu"

Okazało się, na przykład, że do pierwszych kilkunastu milionów

For the first several million, for example, prime numbers ending

http://phys.org/news/2016-03-mathematician-pair-prime-random-thought.html

 

Olivier i Soundararajan przeanalizowali liczby pierwsze do wartości kilkunastu biliardów

vs

In looking at all the prime numbers up to several trillion

http://phys.org/news/2016-03-mathematician-pair-prime-random-thought.html

Edytowane 16 marca 2016 przez Astro

[glaude 40]

Nie chcę się wymądrzać bo daleko mi do waszej wiedzy matematycznej, ale oglądałem bodaj rok temu na Planet serię odcinków o teoriach matematycznych wymagających udowodnienia. W jednym odcinku było o funkcji dzeta, a konkretnie o hipotezie Riemanna. Jeśli mnie pamięć nie myli jakiś fizyk z matematykiem na konferencji naukowej w przerwie na kawę (sic!), wzorem tym opisali orbitale we wszystkich atomach. Czyli liczby pierwsze nie są przypadkowe

Edytowane 16 marca 2016 przez glaude

[Jajcenty 314]

 

 

Jakoś nie śmiałbym wątpić, że masz long. Jaki problem z zastosowaniem "unsigned", czyli olaniu bitu znaku? Może jestem stary, ale było to już w KR C

Nie ma problemu. Jak  mi dasz trochę czasu to sobie sam napiszę cały potrzebny mi soft. Po prostu ucieszyłem się że kompilator daje wsparcie.

Co do reszty to prawdopodobnie ucieszyłem się zbyt wcześnie. Ale i tak mam zamiar sprawdzić ile zajmuje 2³¹ +1 dzieleń, bo jeśli się nie mylę to tyle w najgorszym razie dzieleń potrzebuję by rozebrać 2⁶⁴

Long jest dla mnie egzotyczny. Nawet w bazach trzymam klucz główny w czterobajtowym int.

[Gość Astro]

 

 

W jednym odcinku było o funkcji dzeta, a konkretnie o hipotezie Riemanna. Jeśli mnie pamięć nie myli jakiś fizyk z matematykiem na konferencji naukowej w przerwie na kawę (sic!), wzorem tym opisali orbitale we wszystkich atomach

 

To chyba była zbyt mocna kawa (fizyczna).
https://pl.wikipedia.org/wiki/Funkcje_specjalne

http://mathoverflow.net/questions/54501/riemann-zeta-function-connection-to-quantum-mechanics

No chyba, że (str. 43):

http://gamma.im.uj.edu.pl/~blocki/pmd/pm-gwizdz.pdf

 

 

 

Long jest dla mnie egzotyczny

 

Oj tam; błędy gcc typu "long long is to long", albo "long long long is too long" to kiedyś była normalka.

 

 

 

Nawet w bazach trzymam klucz główny w czterobajtowym int

 

Nie znam się, ale przy statystycznie 64-bitowej maszynie 4-bajtowy int to chyba jakaś zaszłość…

[Afordancja 57]

 

 

Jak  mi dasz trochę czasu to sobie sam napiszę cały potrzebny mi soft. Po prostu ucieszyłem się że kompilator daje wsparcie. Co do reszty to prawdopodobnie ucieszyłem się zbyt wcześnie. Ale i tak mam zamiar sprawdzić ile zajmuje 231 +1 dzieleń

 

 

 Sprawdziłeś? Bo ja dopiero wróciłem z biegania, muszę coś zjeść i zasiadam

ale dzieleńn to chyba za dużo policzyłeś, dzielisz jedynie od 1 do pierwiastek z 2do64 , i to tylko liczby nieparzyste.

 

Druga opcja to jechanie od dołu, czyli sprawdzasz po kolei wszystkie liczby pierwsze, a potem każdą kolejną dzielisz tylko przez liczby pierwsze od 2 do znów pierwiastek z N .

 

Nie wiem co jest szybsze bo drugi przypadek raczej wymagał by tworzenia bazy a to już wolne.

 

 

Uwaga, rzucam tezę

Panowie matematycy sprawdzili jedynie część ogólnej teorii, mianowicie, czy N modulo 10 (gdzie N->liczba pierwsza) rozkłada się jakoś równomiernie, to wszystko, dlaczego więc nie sprawdzić N modulo X (gdzie N->liczba pierwsza, X należy do zbioru liczb całkowitych 3..Y). Ba można sprawdzić czy liczby te z 1 (w systemie 10) na końcu w innych systemach też są jakoś "wyróżnione", czy też jak weźmiemy 3.Y dzielników, to okaże się, że liczby z 1 niczym się nie różnią i każda liczba pierwsza, tylko w innym systemie jest jakoś szczególna.(oczywiście jeszcze tego nie wiem ) .

 

 

4-bajtowy int to chyba jakaś zaszłość

 

No chyba nie . int raczej z definicji ma 4 bajty. (powiedzmy) 

[Gość Astro]

No chyba nie . int raczej z definicji ma 4 bajty

 

Z definicji nie.

The actual size of integer types varies by implementation. The standard only requires size relations between the data types and minimum sizes for each data type:

The relation requirements are that the long long is not smaller than long, which is not smaller than int, which is not smaller than short. As char's size is always the minimum supported data type, all other data types can't be smaller.

The minimum size for char is 8 bits, the minimum size for short and int is 16 bits, for long it is 32 bits and long long must contain at least 64 bits.

The type int should be the integer type that the target processor is most efficient working with. This allows great flexibility: for example, all types can be 64-bit.

https://en.wikipedia.org/wiki/C_data_types

[Jajcenty 314]

Nie znam się, ale przy statystycznie 64-bitowej maszynie 4-bajtowy int to chyba jakaś zaszłość

Też tak myślę, ale u mnie uint32 jest jakby dwa razy szybszy od uint64;

5160 do 9887 ms

 

@Afoancja

 

 

ale dzieleńn to chyba za dużo policzyłeś, dzielisz jedynie od 1 do pierwiastek z 2do64 , i to tylko liczby nieparzyste.

 

sqrt(2^64) = 2^32; tylko nieparzyste 2^31 i +1 za dzielenie przez 2

 

 

            uint CNT = 1000 * 1000 * 1000;

            uint i = 0;

            ulong l = 0;

 

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

            sw.Start();

            do

            {

                i++;

                uint tmp = i % 3;

            }

            while (i < CNT);

            sw.Stop();

            long avgi = sw.ElapsedMilliseconds;

            sw.Reset();

 

            sw.Start();

            do

            {

                l++;

                ulong tmp = l % 3;

            }

            while (l < CNT);

            sw.Stop();

            long avgl = sw.ElapsedMilliseconds;

Edytowane 16 marca 2016 przez Jajcenty

[Gość Astro]

Ja się na hashach przyklejonych do C kompletnie nie znam.

jesteś pewien tożsamości uint z uint32 oraz ulong z uint64? Jeśli system jest 32-bitowy i śmiga na procesorze 64-bitowym, to wynik pewnie nie dziwi. Dla mnie hash znaczy be.

Oczywiście nie to be po A i przed C.

[Afordancja 57]

 

 

Z definicji nie

 

dlatego napisałem "powiedzmy", wypowiadam się jako praktyk.

 

 

 

sqrt(2^64) = 2^32; tylko nieparzyste 2^31 i +1 za dzielenie przez 2

 

ooo kurrr.. nie wiem dlaczego w mózgu "widziałem" 2^32 +1 

 

ok, reset mózgu (zaraz wracam )

[radar 103]

 

 

dzielisz jedynie od 1 do pierwiastek z 2do64 , i to tylko liczby nieparzyste.

nieparzyste bez 5 jeśli już

[Afordancja 57]

nieparzyste bez 5 jeśli już

 

Jakkolwiek by nie patrzeć, masz rację, jakiś uzysk (czasowy) jest. 

Dlatego można iść dalej, i spokojnie dzielić tylko przez pierwsze (w zależności od ilości posiadanej pamięci) 100 milionów liczb pierwszych (strzelam, że dostęp do tablicy będzie szybszy niż strata na dzieleniu przez liczby pomiędzy), a potem już tylko nieparzyste (bez 5, 15, 25, itd. itd.  <- to "itd." jest kluczowe , bo jesteśmy już na wyższych liczbach). 

A tak prawdę mówiąc, to nie wiem czy na IFie nie stracisz więcej czasu (bo domniemam, że chodziło ci o liczby podzielne przez 5) niż na tym podzieleniu

Edytowane 16 marca 2016 przez Afordancja

[radar 103]

IFa i tak masz przy modulo 2. Zawsze można zrobić 4 wątki i każdy będzie dzielił tylko przez jedną końcówkę, odpowiednio 1, 3, 7, 9. Dla małych liczb sito eratostenesa jest najszybsze.

[Afordancja 57]

IFa i tak masz przy modulo 2. Zawsze można zrobić 4 wątki i każdy będzie dzielił tylko przez jedną końcówkę, odpowiednio 1, 3, 7, 9. Dla małych liczb sito eratostenesa jest najszybsze.

 

(akurat żona testuje na mnie robiony miód pitny, a ja popijam piwem więc może coś nie teges)

ja nie dzielę, przez końcówki, ja dzielę przez liczby nieparzyste, aby sprawdzić czy liczba jest pierwsza.

czyli

if (n % x == 0) ->liczba niepierwsza

 

(i nie mam części coś modulo 2) mam x+=2;

 (gdzie x jest z zakresu 3 do DUZO, ale nieparzyste).

 

Możesz mi nakreślić jak się ma do tego Twoja piątka ?

 

(zaraz mi minie fala alkoholu, więc pewnie ogarnę Twój tok rozumowania) 

Edytowane 16 marca 2016 przez Afordancja

[Jajcenty 314]

esteś pewien tożsamości uint z uint32 oraz ulong z uint64? Jeśli system jest 32-bitowy i śmiga na procesorze 64-bitowym, to wynik pewnie nie dziwi. Dla mnie hash znaczy be

 

Tak. uint to 4 bajty;

System jest 64.

Język jak język. Wiele bajerów wspierających, listy, słowniki zdejmują ze mnie 3/4 roboty.

 

Sprawdzenie 2^31 dzieleń to około 20 sekund. Spróbuję się zoptymalizować i puścić to na nieco szybszym procesorze. Zobaczymy ile pierwszych znajdę w rozsądnym czasie (tydzień) odliczając w dół od 2^64.

 

 

nieparzyste bez 5 jeśli już

Tu nie czuję - dlaczego bez 5? To może też wykrywać wielokrotności 5 i nie dzielić?

Edytowane 16 marca 2016 przez Jajcenty

[radar 103]

 

 

Tu nie czuję - dlaczego bez 5? To może też wykrywać wielokrotności 5 i nie dzielić?

A co tu jest do "wykrywania"? Wszystko co się kończy na 0 lub 5 jest podzielne przez 5, czyli nie jest liczbą pierwszą dla n>5

 

 

 

(i nie mam części coś modulo 2) mam x+=2;

I słusznie, a ja dla wątku "1" mam i+=10 dla i(0) == 11, dla "3" mam i+=10 dla i(0)==13 itd.

[Gość Astro]

 

 

Tak

 

Nie wiem, może wywaliłbym deklarację uint/ ulong zmiennej tmp przed pętlę?

[Weinreb 0]

Słyszeliście pewnie o projekcie BOINC? 

 

http://www.primegrid.com , 

 

http://primes.utm.edu/primes/home.php ,

 

https://oeis.org/A000040,

 

polecam też zerknąć tu:

 

http://factordb.com

[Xitami 1]

Dwa nieporozumienia

1 - przecie nie chodzi o najmłodszą cyfrę

2 - testowanie pierwszości przez dzielenie

[radar 103]

 

 

Dwa nieporozumienia 1 - przecie nie chodzi o najmłodszą cyfrę 2 - testowanie pierwszości przez dzielenie

No ba, testy "pierwszości" istnieją, ale są probabilistyczne i/lub opierają się na jeszcze nieudowodnionych twierdzeniach.

 

My tu mówimy o amatorskim obliczaniu, które mimo "amatorskości" wykracza zakresem dużo dalej niż badali naukowcy z artykułu. Przy amatorskim algorytmie, gdzie dzielimy, najmłodsza cyfra ma sens, bo testujesz tylko 4 liczby z 10.

[Jajcenty 314]

 

 

A co tu jest do "wykrywania"? Wszystko co się kończy na 0 lub 5 jest podzielne przez 5, czyli nie jest liczbą pierwszą dla n>5

 

Och, tak. Ale dopóki trzymamy się poniżej 19 cyfr znaczących to sprawdzanie podzielników na podzielność przez 5 dokłada roboty. Chyba że umiemy z 2n+1 wywalić te podzielne przez 5 nie używając modulo?

 

 

 

Nie wiem, może wywaliłbym deklarację uint/ ulong zmiennej tmp przed pętlę?

Nic to nie zmieniło, ale rzecz jest do dalszego śledztwa - mimo nastaw x64 kompilator z uporem produkuje win32. Włoski strajk?

 

W każdym razie mój naiwny, jednowątkowy algorytm dostarczył 100 liczb pierwszych w 54 minuty, na dobę jakieś 2500. Obciążenie procesora mniejsze od 25% Czyli kicha, słabo i nędza z mułem. Postawiłem sobie za punkt honoru, że w wolnym czasie wyduszę z niego 10 razy więcej.

 

Oto największy 64 bitowy prime: 18446744073709551557

 

 

W jednym odcinku było o funkcji dzeta, a konkretnie o hipotezie Riemanna. Jeśli mnie pamięć nie myli jakiś fizyk z matematykiem na konferencji naukowej w przerwie na kawę (sic!), wzorem tym opisali orbitale we wszystkich atomach.

To chyba nadaje się jako osobny wątek do dyskusji bo w ferworze walki nam to umknęło. Widziałem jedną alternatywną teorię orbitali atomowych, ale jej twórca nie zyskał sobie uznania.