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

[Jajcenty 314]

 

 

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 10ⁿ do 10ⁿ⁺¹. Mi wyszło ok (3/n)*10ⁿ zatem nie wydaje się by metoda "przez odgaść" czy jakakolwiek inna intuicyjno-losowa mogła coś tu zdaiałać.

[nk_1 0]

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

[Matcher 2]

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?

[nk_1 0]

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.

[Matcher 2]

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

[nk_1 0]

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

[taśma9 1]

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.

[Matcher 2]

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

[taśma9 1]

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

[Afordancja 57]

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

 

 

[taśma9 1]

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