Skocz do zawartości
Forum Kopalni Wiedzy
KopalniaWiedzy.pl

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

Rekomendowane odpowiedzi

 

 

Nie wiem tylko czemu w tej spirali liczba LP wydaje się stała, choć wiadomo,że im dalej jedziemy tym mniej po drodze znajdziemy.

Słowo "wydaje się" jest właściwe. Nie wiem jaki obrazek oglądałeś, ale z konieczności widziałeś może kilkadziesiąt tysięcy LP (na wiki drugi obrazek to 39K LP). Dla dużych wartości N wyraz N/ln(N) jest praktycznie nieodróżnialny od prostej:

wykresik

 

spróbuj oszacować ile jest liczb pierwszych w przedziale 10n do 10n+1. Mi wyszło ok (3/n)*10n zatem nie wydaje się by metoda "przez odgaść" czy jakakolwiek inna intuicyjno-losowa mogła coś tu zdaiałać. :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jest jeszcze inny sposób analizy liczb pierwszych pokazany poniżej. Pozwala na większy zakres analizy liczb pierwszych np. w Excelu. Algorytm pokazuje, że liczby złożone nie są rozmieszczone przypadkowo lecz są w określonych od siebie odstępach.

Sito Małgorzaty opisane jest pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhhzzvgOxdib8Y_rW

 

Poniżej przykładowe makro w Excelu:

Sub sito()

Dim j, i As Long

Dim a, b As Long

Dim t As Boolean

Dim f As Boolean

Dim x_max As Long

Dim x As Long

Dim yp As Long

Dim pk As Integer

Dim pky As Integer

Dim pk_max As Integer

Dim pk_min As Integer

Range("B:Z").ClearContents

‘ilosc danych w kadej kolumnie np. 1040000

x_max = Range("A1").Text

‘ilosc kolumn – wartosc max 25

pk_max = Range("A2").Text

‘ zaczynamy od 2 kolumny

pk = 2

pky = 2

pk_min = 2

pk_max = pk_max + 1

t = True

‘ wartosc pocztkowa dla iteracji

yp = 1

i = 0

Do

i = i + 1

‘ wartosc pocztkowa x dla danej iteracji i

x = yp

‘ wyliczenie wartosci a i b

a = 1 + 2 * i

If t Then

b = 4 * i + 3

Else

b = 4 * i + 1

End If

‘ ustawienie kolejnoci a czy b – t dla iteracji i , f dla poditeracji

f = t

If Cells(i, pk).Value <> 1 Then

If f Then

x = x + b

yp = x + a

Else

x = x + a

yp = x + b

End If

‘zaznaczenie elementla danej iteracji

For j = pk_min To pk_max

Do While x < x_max

Cells(x, j) = 1

If f Then

x = x + a

Else

x = x + b

End If

f = Not (f)

Loop

x = x – x_max + 1

Next j

Else

yp = yp + a + b

End If

If Not (yp < x_max) Then

yp = yp – x_max + 1

pky = pky + 1

End If

pk_min = pky

t = Not (t)

Loop Until (pky > pk_max)

End Sub

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Na ostatniej tabelce są liczby x zaznaczone na niebiesko. Że niby to ma być taki rosnący ciąg liczbowy, który pokazuje pewną regularność liczb złożonych?

Jeśli tak, to jaka będzie kolejna liczba zaznaczona na niebiesko po liczbie 16?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Załóżmy,że analizę liczb robimy do x=25.

Napiszę w skrócie:

1. Iteracja dla y=1 b=7 ia=3

Wyznaczone liczby dla y=1: 8,11,18,21,28

2. Iteracji y=2 b=9 i a=5

Wyznaczone liczby dla y=2: 16,25,30

3. Iteracja y=3 b=15 i a=7

Kończymy bo 25 jest liczbą do której analizujemy.

 

Zatem liczby wyznaczone przez algorytm Sito Małgorzaty w przedziale (1,25) są następujące:

8,11,16,18,21,25

 

W algorytmie na początku należy określić maksymalną wartość x, dla której przeprowadzamy obliczenia.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jest jeszcze inny sposób analizy liczb pierwszych pokazany poniżej. Pozwala na większy zakres analizy liczb pierwszych np. w Excelu. Algorytm pokazuje, że liczby złożone nie są rozmieszczone przypadkowo lecz są w określonych od siebie odstępach.

 

Jak liczby złożone są rozmieszczone w określonych odstępach? Przecież występują jedna przy drugiej :-]

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Porównaj odstępy (naprzemiennie a i b) dla danej iteracji.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Mnie osobiście jakoś to Sito Małgorzaty nie przekonuje. Brak jakichkolwiek materiałów w wójku google. Może przy bardzo dużych liczbach pozwala skoncentrować się tylko na tych które są pierwsze ? jeśli tak jest, to fajnie, tylko że robiąc sito, które wylewa się na dysk, osiągnę dużo większą wydajność kosztem pamięci dyskowej.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Może ktoś wytłumaczyć fenomen tego sita? Co dokładnie ono wyznacza?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

0 ... 100 000 000 020   time:   52.441000000003456

nowa wersja w przygotowaniu :)

w trybie jednowątkowym jest 52.441000000003456 vs primesievie 17.65

czas może ulec zmianie na gorsze .. ale też na lepsze

10**12 wychodzi około 12 minut

wszystko podane w trybie jednowątkowym, a algorytm przygotowany jest już pod wielowątkowość

wychodzi że w primesieve jest około 3 razy szybsze od algorytmu w javie

ciekawe czy uda mi się wycisnąć coś więcej :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
14 godzin temu, taśma9 napisał:

10**12 wychodzi około 12 minut

łoo już zapomniałem o tym wątku, 10**12 to zakres który badasz? ile tam było pierwszych ?

Już nie pamiętam mojego tempa, już nawet nie mam tego programu :/

 

 

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
8 godzin temu, Afordancja napisał:

łoo już zapomniałem o tym wątku, 10**12 to zakres który badasz? ile tam było pierwszych ?

Już nie pamiętam mojego tempa, już nawet nie mam tego programu :/

 

 

Na razie program jest w przygotowaniu, rozwinięcie poprzedniego, nie sądziłem że z javy można tyle wyciągnąć. Teraz zrobiłem że sito jest robione kawałkami dzięki temu zajmuje niewiele pamięci i działa szybciej, z tego też względu nie jestem w stanie powiedzieć ile jest pierwszych w zakresie 1 ... 10**12 ale gdy sprawdzam segmentami to ilość się zgadza. Jak ogarnę podział segmentów do końca to zrobię sumowanie i wtedy będzie wiadomo. Już nie pamiętasz :). Właśnie ja mam takie tempo wracam po pół roku, po roku do tematu gdy mam już przemyślane nowe pomysły i tak w ślimaczym tempie sobie pisze :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

×
×
  • Dodaj nową pozycję...