Liczby pierwsze nie są rozłożone losowo?
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.
Komentarze (285)
Afordancja, 16 marca 2016, 15:30
(ż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, 16 marca 2016, 16:12
Zaraz, zaraz, a dla pierwszych 100 to prawdopodobieństwo także dla "1" wynosi 18,5%?
Jajcenty, 16 marca 2016, 16:14
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 10100 by efekcie być całkowicie losowym jeśli tylko przedział jest szerszy niż 10200
Te kilkanaście biliardów czyli 1015 to coś dziwnego. Mój laptop bez łaski obsługuje liczby całkowite do 9x1018. 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,8x1019. Ha!
ulong.MaxValue = 18 446 744 073 709 551 615
Uriziel, 16 marca 2016, 18:25
Nie rozumiem dlaczego wyniki podane są w formie
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)
Rozrzut wartości jest największy dla ostatniej cyfry równej 9 (cały zakres do 32452843):
Przy dostępnej dla nich mocy obliczeniowej powinni sprawdzić to dla przynajmniej 50 000 000 liczb pierwszych.
Gość Astro, 16 marca 2016, 18:46
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
Pełna zgoda. Mówi to nawet fizyk.
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…
bo to tak "dla przykładu"
http://phys.org/news/2016-03-mathematician-pair-prime-random-thought.html
vs
http://phys.org/news/2016-03-mathematician-pair-prime-random-thought.html
glaude, 16 marca 2016, 19:43
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
Jajcenty, 16 marca 2016, 20:05
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 231 +1 dzieleń, bo jeśli się nie mylę to tyle w najgorszym razie dzieleń potrzebuję by rozebrać 264
Long jest dla mnie egzotyczny. Nawet w bazach trzymam klucz główny w czterobajtowym int.
Gość Astro, 16 marca 2016, 20:35
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
Oj tam; błędy gcc typu "long long is to long", albo "long long long is too long" to kiedyś była normalka.
Nie znam się, ale przy statystycznie 64-bitowej maszynie 4-bajtowy int to chyba jakaś zaszłość…
Afordancja, 16 marca 2016, 21:09
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 ) .
No chyba nie . int raczej z definicji ma 4 bajty. (powiedzmy)
Gość Astro, 16 marca 2016, 21:15
Z definicji nie.
https://en.wikipedia.org/wiki/C_data_types
Jajcenty, 16 marca 2016, 21:16
Też tak myślę, ale u mnie uint32 jest jakby dwa razy szybszy od uint64;
5160 do 9887 ms
@Afoancja
sqrt(2^64) = 2^32; tylko nieparzyste 2^31 i +1 za dzielenie przez 2
Gość Astro, 16 marca 2016, 21:26
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, 16 marca 2016, 21:26
dlatego napisałem "powiedzmy", wypowiadam się jako praktyk.
ooo kurrr.. nie wiem dlaczego w mózgu "widziałem" 2^32 +1
ok, reset mózgu (zaraz wracam )
radar, 16 marca 2016, 21:29
nieparzyste bez 5 jeśli już
Afordancja, 16 marca 2016, 21:36
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
radar, 16 marca 2016, 21:42
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, 16 marca 2016, 21:47
(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)
Jajcenty, 16 marca 2016, 22:00
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.
Tu nie czuję - dlaczego bez 5? To może też wykrywać wielokrotności 5 i nie dzielić?
radar, 16 marca 2016, 22:15
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 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, 16 marca 2016, 22:16
Nie wiem, może wywaliłbym deklarację uint/ ulong zmiennej tmp przed pętlę?
Weinreb, 17 marca 2016, 10:51
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, 17 marca 2016, 11:19
Dwa nieporozumienia
1 - przecie nie chodzi o najmłodszą cyfrę
2 - testowanie pierwszości przez dzielenie
radar, 17 marca 2016, 11:50
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, 17 marca 2016, 12:07
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?
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
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.