Skocz do zawartości


Zdjęcie

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


  • Zaloguj się, aby dodać odpowiedź
275 odpowiedzi w tym temacie

#1 KopalniaWiedzy.pl

Napisano 16 marzec 2016 - 15:17

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
  • 0

Reklamy Google

#2 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 16 marzec 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! :D

 

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ć? :D


  • 0

#3 thikim

thikim

    Kierownik robót

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3938 postów

Napisano 16 marzec 2016 - 16:12

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

#4 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 16 marzec 2016 - 16:14

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 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 :D

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


Użytkownik Jajcenty edytował ten post 16 marzec 2016 - 16:27

  • 0

#5 Uriziel

Uriziel

    Górnik

  • Nowi użytkownicy
  • Pip
  • 2 postów

Napisano 16 marzec 2016 - 18:25

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.


  • 0

#6 ~Astro

~Astro
  • Goście

Napisano 16 marzec 2016 - 18:46

gdzie to potem ogłosić? :D

Zaraz się z Afordancją za to weźmiemy :D

 
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 10100

 
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...om-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...om-thought.html


Użytkownik Astro edytował ten post 16 marzec 2016 - 18:48


#7 glaude

glaude

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 740 postów

Napisano 16 marzec 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 :)

Użytkownik glaude edytował ten post 16 marzec 2016 - 19:44

  • 0

#8 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 16 marzec 2016 - 20:05

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 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.


  • 0

#9 ~Astro

~Astro
  • Goście

Napisano 16 marzec 2016 - 20:35

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...nkcje_specjalne

http://mathoverflow....antum-mechanics

No chyba, że (str. 43):

http://gamma.im.uj.e...d/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ść… ;)



#10 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 16 marzec 2016 - 21:09

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ś? :D 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) 


  • 0

#11 ~Astro

~Astro
  • Goście

Napisano 16 marzec 2016 - 21:15

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

 
Z definicji nie. :D

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...ki/C_data_types



#12 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 16 marzec 2016 - 21:16

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 :D

 

 

            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;

Użytkownik Jajcenty edytował ten post 16 marzec 2016 - 21:22

  • 0

#13 ~Astro

~Astro
  • Goście

Napisano 16 marzec 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. ;)



#14 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 16 marzec 2016 - 21:26

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 ;) )


  • 0

#15 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 16 marzec 2016 - 21:29

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

nieparzyste bez 5 jeśli już


  • 0

#16 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 16 marzec 2016 - 21:36

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


Użytkownik Afordancja edytował ten post 16 marzec 2016 - 21:38

  • 0

#17 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 16 marzec 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.


  • 0

#18 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 16 marzec 2016 - 21:47

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) 


Użytkownik Afordancja edytował ten post 16 marzec 2016 - 21:48

  • 0

#19 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 16 marzec 2016 - 22:00

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ć?


Użytkownik Jajcenty edytował ten post 16 marzec 2016 - 22:08

  • 0

#20 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 16 marzec 2016 - 22:15

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.


  • 0