Panopticum - strona główna

Liczby pierwsze

- ilość, rozmieszczenie, wzory, Hipoteza Goldbacha



Liczba pierwsza to liczba naturalna, mająca dokładnie dwa podzielniki: dzieli się przez 1 oraz przez samą siebie (liczba 1 nie zalicza się do liczb pierwszych, gdyż ma tylko 1 podzielnik). Liczby naturalne większe od 1, nie będące liczbami pierwszymi to liczby złożone; można je rozłożyć na czynniki będące liczbami pierwszymi.
Początkowe liczby pierwsze to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, ...
Stąd można ściągnąć skompresowany plik tekstowy zawierający 78.498 początkowych liczb pierwszych ( z zakresu do 1.000.000 ).


Euklides
(ok. 365 p.n.e. - 300 p.n.e.)
Liczb pierwszych jest nieskończenie wiele. Udowodnił to już ponad dwa tysiące lat temu Euklides.
Załóżmy, że zbiór liczb pierwszych jest ograniczony. Utwórzmy iloczyn tych wszystkich liczb. Do tego iloczynu dodajmy 1. Otrzymana liczba nie będzie się dzielić przez żadną liczbę z naszego zbioru liczb pierwszych, gdyż zawsze pozostanie reszta 1. Wynika z tego, że albo otrzymana liczba jest też liczbą pierwszą, albo dzieli się ona przez jakąś inną liczbę pierwszą, nie zawartą w naszym zbiorze liczb pierwszych. W obydwu przypadkach oznacza to, że otrzymujemy nową liczbę pierwszą, co jest sprzeczne z założeniem, że zbiór zawierał wszystkie liczby pierwsze.
Oczywiście, aby sprawdzać czy dana liczba jest liczbą pierwszą, nie trzeba wykonywać prób jej dzielenia przez wszystkie liczby naturalne mniejsze od danej liczby (wystarcza tu powiedzieć: nie większe od pierwiastka z danej liczby), lecz tylko przez liczby pierwsze. Jeśli liczba nie dzieli się przez żadną z liczb pierwszych, to nie dzieli się także przez żadną z liczb złożonych (które są przecież iloczynami liczb pierwszych).
Gęstość rozmieszczenia liczb pierwszych wśród liczb naturalnych maleje wraz ze wzrostem tych liczb.
W zbiorze początkowych 20 liczb naturalnych jest 8 liczb pierwszych ( 2,3,5,7,11,13,17,19 ), czyli 40%. W zakresie od 1 do 10.000 jest 1.229 liczb pierwszych czyli 12,29%, a w zakresie do 1.000.000 jest ich 78.498 tzn. ok. 7,8%.
W 1896r. Hadamard i de la Valée-Poussin określili, że dla dużych N wśród liczb 1, 2, 3, ... N jest w przybliżeniu N/ln(N) liczb pierwszych, czyli ułamek 1/ln(N) oznaczałby udział liczb pierwszych w zbiorze liczb naturalnych 1 ... N.


Zakres liczb
naturalnych
Ilość liczb
pierwszych
Udział
%
Ilość LP
narast.
Udział
%
100%/ln(N)
/N - środek
zakresu/
1 - 10.000 1.22912,29 1.22912,29 11,74
10.001 - 20.000 1.03310,332.26211,3110,40
20.001 - 30.000 9839,833.24510,82 9,87
30.001 - 40.000 9589,584.20310,51 9,56
40.001 - 50.000 9309,305.13310,27 9,33
50.001 - 60.000 9249,246.05710,10 9,16
60.001 - 70.000 8788,786.9359,91 9,02
70.001 - 80.000 9029,027.8379,80 8,91
80.001 - 90.000 8768,768.7139,68 8,81
90.001 - 100.000 8798,799.5929,59 8,72
...... ......... ...
19.990.001
- 20.000.000
5965,961.270.6176,35 5,95
Wykres poniżej (sporządzony wg tabeli, której fragment widać obok) przedstawia procentowy udział liczb pierwszych wśród liczb naturalnych od 1 do 20.000.000.

2.000 żółtych punktów oznacza procentowe udziały w zakresach po 10.000 kolejnych liczb naturalnych. Widać, że te "bieżące gęstości" ulegają znaczącym fluktuacjom.
Czerwona linia określa średni procentowy udział LP narastająco - liczony od początku.
Pomarańczowa linia odzwierciedla procentowe udziały LP określone wg wzoru Hadamarda i de la Valée-Poussin'a. Widoczne jest, że linia ta wskazuje na średnie "bieżące gęstości" (żółte punkty). Oznacza to, że ułamek 1/ln(N) określa lokalną "gęstość" liczb pierwszych w okolicy liczby N a nie udział LP w zbiorze liczb 1 ... N, jak to sugerowali wymienieni matematycy.




Jeśli 1/ln(N) oznacza lokalną gęstość liczb pierwszych w otoczeniu liczby N, to ilość LP w dowolnym zakresie liczb naturalnych, np. od a do b, określimy poprzez rozwiązanie całki:
Wstępnie przeprowadzone obliczenie wartości tej całki dla stosunkowo niewielkich N ( sumowanie wartości wyrażenia 1/lnN dla kolejnych liczb naturalnych od 2 do N ) wykazuje, że otrzymujmy wartości wyższe od rzeczywistych ilości liczb pierwszych, ale względna wielkość tego odchylenia zmniejsza się w miarę wzrostu N:




Jacques-Salomon Hadamard
(1865 - 1963)
NRzeczywista
ilość liczb
pierwszych
Ilość LP
wg całki
Odchylenie
%
104650,0
50151820,0
100253020,0
500951027,4
1.0001681775,4
2.0003033154,3
3.0004304433,0
4.0005505652,7
5.0006696842,2
10.0001.2291.2461,4
50.0005.1335.1660,6
100.0009.5929.6290,4
500.00041.53841.6060,16
1.000.00078.49878.6270,16

Przy próbie całkowania ( przez części ) okaże się, że otrzymamy szereg nieskończony:
Szereg niestety nie jest zbieżny: począwszy od pewnego wyrazu ( zależnie od wartości N ) licznik ułamka rośnie szybciej od mianownika i wszystkie następne wyrazy rosną, dążąc do nieskończoności. Gdyby to nas nie zniechęciło i uparcie będziemy kontynuować obliczenie całki oznaczonej ( dla ułatwienia można przyjąć np.  a = e,  b = e2,  gdzie e - podstawa logarytmów naturalnych ) odejmując odpowiadające sobie wyrazy ( Wi(b)-Wi(a) ), powstały wynikowy szereg będzie tym razem dążył do minus nieskończoności.
Ale nie ma sytuacji bez wyjścia. Zróbmy podstawienie:
x = lnN   czyli:   N = ex     dN = ex . dx
Nasza całka będzie wyglądać tak:

Wyrażenie ex można łatwo rozwinąć w szereg Maclaurina:
ex = 1   +  
x1
1!
  +  
x2
2!
  +  
x3
3!
  +  
x4
4!
  + . . .

Dzieląc obustronnie przez x otrzymujemy nasze wyrażenie podcałkowe:
ex
x
  =  
1
x
  +  1  +  
x
2!
  +  
x2
3!
  +  
x3
4!
  + . . .

Całkując ten szereg, wyraz po wyrazie, uzyskujemy rozwiązanie całki:
lnx   +  x  +  
x2
2.2!
  +  
x3
3.3!
  +  
x4
4.4!
  + . . .

czyli, podstawiając znowu x = lnN, otrzymujemy formułę określającą ilość liczb pierwszych w zakresie liczb naturalnych 1 ... N (można tu sobie darować wartość całki oznaczonej dla dolnego zakresu całkowania: dla N=2 wynosi ona poniżej 1):
lnlnN   +  lnN  +  
(lnN)2
2.2!
  +  
(lnN)3
3.3!
  +  
(lnN)4
4.4!
  + . . .

Tym razem otrzymaliśmy "porządny" szereg, w którym wyrazy dosyć szybko (zależnie od wartości N) zaczynają maleć, dążąc do zera.
Zgodnie z tym co już wyżej powiedziano, wielkości uzyskiwane z zastosowaniem tego szeregu są nieco wyższe od rzeczywistych ilości liczb pierwszych. Natomiast bardzo dobrą zgodność otrzymuje się uwzględniając w obliczeniach tylko pewną ilość początkowych wyrazów zależną od N. Numer ostatniego wyrazu, który należy uwzględnić (wyraz lnlnN traktuję jako zerowy, czyli wyraz numer k będzie wynosił: (lnN)k/k.k! ):

k = 5.(logN - 1)   /występuje tu logarytm dziesiętny/

NRzeczywista
ilość liczb
pierwszych
Pełna wartość całki Wartość do wyrazu numer k
WartośćOdchylenie
%
kWartośćOdchylenie
%
1002530+20,0 5250,00
1.000168177+5,36 10169+0,60
10.0001.2291.246+1,38 151.230+0,08
100.0009.5929.629+0,39 209.595+0,03
1.000.00078.49878.627+0,16 2578.545+0,06
10.000.000664.579664.918+0,05 30664.718+0,02
100.000.0005.761.4555.762.209+0,01 355.761.704+0,004
1.000.000.00050.847.53450.849.234+0,003 4050.847.930+0,0008
10.000.000.000455.052.511455.055.614+0,0007 45455.052.183-0,0001
100.000.000.0004.118.054.8134.118.066.410+0,0003 504.118.057.242+0,0001
1.000.000.000.00037.607.912.01837.607.951.903+0,00015537.607.925.537+0,00004


Dokonywanie obliczeń z zastosowaniem szeregu jest niezbyt wygodne i dlatego można próbować eksperymentalnie znaleźć w miarę prosty wzór, wykazujący dostateczną zgodność z danymi rzeczywistymi.
Wiadomym jest, że żaden wzór nie może się tutaj idealnie sprawdzać, gdyż "gęstość" rozmieszczenia liczb pierwszych w ciągu liczb naturalnych zmienia się "skokowo" ( przy każdorazowym pojawieniu się takiej liczby pierwszej ).
Dosyć dobrą zgodność otrzymujemy przy zastosowaniu wzoru:
N/(ln(N) - 1)   co można zapisać inaczej:   N/ln(N/e)
lub, z dobrym przybliżeniem, jeszcze inaczej:    N2/ln(N!).

Średnie odchylenie od rzeczywistych wielkości, ilości LP wyliczonych wg tego wzoru dla 2.000 "punktów pomiarowych" w zakresie liczb naturalnych 1 ... 20.000.000, wynosi ok. 0,50% ( a maksymalne 0,96% ). Dla porównania: przy zastosowaniu wzoru Hadamarda i de la Valée-Poussin'a N/ln(N) śr. odchylenie wynosi 6,82% a maksymalne 11,66%.


Adrien Marie Legendre
(1752 - 1833)
Adrien Marie Legendre podał w 1798 roku wzór:
N/(ln(N) - 1,08366)
Tutaj śr. odchylenie wynosi już tylko 0,065% a maksymalne 0,25%. Wartość 1,08366 jest czasem zwana stałą Legendre'a.

Jeszcze lepsze dopasowanie ( śr. odchyl. 0,018%, maks. 0,23% ) można uzyskać po dalszej korekcie:
N/(ln(N) - 1,0734075)

Tabela pokazuje jaka jest zgodność z rzeczywistością ww. wzorów przy większych wartościach N.

NRzeczywista
ilość liczb
pierwszych
N/ln(N)
/Hadamard i de la Valée-Poussin/
N/(ln(N) - 1)N/(ln(N) - 1,08366)
/Legendre/
N/(ln(N) - 1,0734075)
Ilość LPOdch.
%
Ilość LPOdch.
%
Ilość LPOdch.
%
Ilość LPOdch.
%
10.0001.2291.086-11,661.218-0,901.231+0,121.2290,00
100.0009.5928.686-9,459.512-0,839.588-0,049.579-0,14
1.000.00078.49872.382-7,7978.030-0,6078.543+0,0678.480-0,02
10.000.000664.579620.421-6,64661.459-0,47665.140+0,08664.686+0,02
100.000.0005.761.4555.428.681-5,785.740.304-0,375.768.004+0,115.764.595+0,05
1.000.000.00050.847.53448.254.942-5,1050.701.542-0,2950.917.519+0,1450.890.952+0,09
10.000.000.000455.052.511434.294.482-4,56454.011.971-0,23455.743.004+0,15455.530.157+0,10
100.000.000.0004.118.054.8133.948.131.654-4,134.110.416.301-0,194.124.599.869+0,164.122.856.417+0,12
1.000.000.000.00037.607.912.01836.191.206.825-3,7737.550.193.650-0,1537.668.527.415+0,1637.653.985.575+0,12
10.000.000.000.000346.065.536.839334.072.678.387-3,47345.618.860.221-0,13346.621.096.885+0,16346.497.960.768+0,12

Oczywiście jeszcze lepsze dopasowania można by uzyskać poprzez dalsze korekty i wprowadzanie dodatkowych współczynników, lecz takie formuły nie są zbyt eleganckie.
Przykładowo, dokładniejsze przybliżenia możemy uzyskać poprzez zastosowanie wzoru:
0,997344779.N/(lnN - 1,110432659) - 2
Wzór ten generuje nam następujące ilości liczb pierwszych:

NRzeczywista ilość
liczb pierwszych
Ilość LP
uzyskana wg wzoru
Odchylenie
od rzecz. ilości
%
10.0001.2291.2290,00
100.0009.5929.586-0,067
1.000.00078.49878.4980,00
10.000.000664.579664.555-0,004
100.000.0005.761.4555.761.584+0,002
1.000.000.00050.847.53450.851.640+0,008
10.000.000.000455.052.511455.088.177+0,008
100.000.000.0004.118.054.8134.118.195.721+0,003
1.000.000.000.00037.607.912.01837.606.434.721-0,004
10.000.000.000.000346.065.536.839346.021.848.325-0,013

Dla 2.000 "punktów pomiarowych" z zakresu 1 ... 20.000.000 powyższy wzór daje nam średnie odchylenie od rzeczywistych wielkości w wys. 0,021% ( maksymalnie 0,198% ).


Marin Mersenne (1588 - 1648)
Na przestrzeni wieków wielu sławnych matematyków jak i zwykłych amatorów próbowało znaleźć wzory generujące w prosty sposób liczby pierwsze. Ideałem byłby wzór, z którego przy podstawianiu kolejnych liczb naturalnych ( bez żadnego ograniczenia ) otrzymywalibyśmy kolejne liczby pierwsze, ale wydaje się, że niemożliwe jest istnienie takiego wzoru.
Jednym z bardziej znanych, a to za sprawą internetowego programu GIMPS, jest wzór, który w 1644r. podał francuski mnich, a jednocześnie filozof i matematyk oraz wielki popularyzator nauki, Marin Mersenne:

MP = 2P - 1

Podstawiając za P liczby pierwsze otrzymujemy w wyniku nierzadko także liczby pierwsze ( np. dla P = 2, 3, 5, 7, 13, 17, ... ).
W realizowanym od stycznia 1996r. programie GIMPS (Great Internet Mersenne Prime Search - Wielkie Internetowe Poszukiwanie Liczb Pierwszych Mersenne'a ) uczestniczą tysiące chętnych z całego świata. Za pomocą ściągniętego programu testuje się wybrany zakres wykładników. Na odkrywców czeka sława a także pieniądze!
W ramach tego programu w dniu 23.08.2008r. odkryta została 45. wielka liczba pierwsza Mersenne'a:   243.112.609 - 1. Liczba ta ma 12.978.189 cyfr. Poprzednia 44. liczba (232.582.657 - 1 ; 9.808.358 cyfr) odkryta była w 2006 roku.
Za pobijane tutaj rekordy ustanawiane są nagrody pieniężne (tak było m.in. z pierwszą liczbą o minimum 10 mln cyfr).
Strona programu GIMPS: http://www.mersenne.org/prime.htm.


Leonhard Euler (1707 - 1784)
Jednymi z prostszych wyrażeń generujących stosunkowo dużo liczb pierwszych są trójmiany kwadratowe.
Wspomniany już Adrien Marie Legendre znalazł wyrażenie   2n2 + 29. Dla n = 1, 2, 3, ... 28 otrzymamy 28 róznych liczb pierwszych.
Leonhard Euler podał w 1772r. wzór:   n2 - n + 41. Z tego wzoru przy n = 1, 2, ... 40 otrzymamy 40 różnych liczb pierwszych. Wyrażenie to, po podstawieniu n = i - 39 można przekształcić następująco:  i2 - 79i + 1601. Ten wzór daje nam 79 liczby pierwsze dla i = 1, 2, ... 79, lecz 39 z tych liczb powtarza się.

Dwa ostatnie wzory należą do tej samej serii, generującej 40 różnych LP i ewentualnie część z tych liczb powtórnie:

 n2 - n + 41  40 LP; bez powtórzeń ( Euler )
 n2 - 3n + 43  41 LP; w tym 1 liczba powtarza się
 n2 - 5n + 47  42 LP; w tym 2 liczby powtarzają się
  . . .   
 n2 - 79n +1601  79 LP; w tym 39 liczb powtarza się ( Euler )
 n2 - 81n +1681  80 LP; w tym 40 liczb powtarza się

Ostatni wzór to najlepszy jaki udało mi się znaleźć, generujący liczby pierwsze dla największej ilości początkowych liczb naturalnych. Nie znalazłem, jak na razie, żadnego wzoru, który dawałby więcej niż 40 różnych liczb pierwszych w początkowej serii.
W poniższej tabeli zestawione są liczby pierwsze wygenerowane przy pomocy niektórych wzorów.

nLegendreEulern2
- 3n
+ 43
n2
- 5n
+ 47
n2
- 81n
+ 1681
2n2
- 116n
+ 1711
3n2
- 135n
+ 1541
4n2
- 166n
+ 1763
6n2
- 354n
+ 5251
9n2
- 249n
+ 1763
2n2 + 29n2 - n
+ 41
n2 - 79n
+1601
Ogółem LP: 284079414280 5744405840
Unikalnych LP: 2840404040 402922402940
131411.52341431.6011.5971.4091.6014.9031.523
237431.44741411.5231.4871.2831.4474.5671.301
347471.37343411.4471.3811.1631.3014.2431.097
461531.30147431.3731.2791.0491.1633.931911
579611.23153471.3011.1819411.0333.631743
6101711.16361531.2311.0878399113.343593
7127831.09771611.1639977437973.067461
8157971.03383711.0979116536912.803347
919111397197831.0338295695932.551251
10229131911113979717514915032.311173
112711518531311139116774194212.083113
123171737971511318536073533471.86771
133671977431731517975412932811.66347
144212236911971737434792392231.47141
154792516412231976914211911731.29153
165412815932512236413671491311.12383
1760731354728125159331711397967131
186773475033132815472718371823197
197513834613473135032295953691281
208294214213833474611914143571383
219114613834213834211572941463503
229975033474614213831272347367641
231.0875473135034613471012361283797
241.181593281547503313792983211971
251.27964125159354728161411131511.163
261.38169122364159325147591511031.373
271.4877431976916412233783197671.601
281.59779717374369119731113251431.847
29 85315179774317329149313312.111
30 91113185379715131191383312.393
31 97111391185313137239461432.693
32 1.0339797191111347293547673.011
33 1.097831.03397197613536411033.347
34 1.163711.0971.03383794197431513.701
35 1.231611.1631.097711014918532114.073
36 1.301531.2311.163611275699712834.463
37 1.373471.3011.231531576531.0973674.871
38 1.447431.3731.301471917431.2314635.297
39 1.523411.4471.373432298391.3735715.741
40 1.601411.5231.447412719411.5236916.203
41  431.6011.523413171.049 823 
42  47 1.601433671.163 967 
43  53  474211.283 1.123 
44  61  534791.409 1.291 
45  71  61541  1.471 
46  83  71607  1.663 
47  97  83677  1.867 
48  113  97751  2.083 
49  131  113829  2.311 
50  151  131911  2.551 
51  173  151997  2.803 
52  197  1731.087  3.067 
53  223  1971.181  3.343 
54  251  2231.279  3.631 
55  281  2511.381  3.931 
56  313  2811.487  4.243 
57  347  3131.597  4.567 
58  383  347   4.903 
59  421  383     
60  461  421     
61  503  461     
62  547  503     
63  593  547     
64  641  593     
65  691  641     
66  743  691     
67  797  743     
68  853  797     
69  911  853     
70  971  911     
71  1.033  971     
72  1.097  1.033     
73  1.163  1.097     
74  1.231  1.163     
75  1.301  1.231     
76  1.373  1.301     
77  1.447  1.373     
78  1.523  1.447     
79  1.601  1.523     
80     1.601     

Poszukiwanie tego typu wzorów w obecnych czasach, gdy mamy do dyspozycji komputery, nie sprawia zbytnich trudności. Podziwiać należy natomiast XVIII-wiecznych matematyków nie posiadających nawet zwykłego elektronicznego kalkulatora.


Christian Goldbach (1690 - 1764)
Duże pieniądze czekają też na tego, kto udowodni prawdziwość Hipotezy Goldbacha. Wydawnictwo Faber and Faber w Wlk. Brytanii ufundowało na ten cel 1.000.000 dolarów.
Sama hipoteza, postawiona jeszcze w 1742 roku przez rosyjskiego matematyka Christiana Goldbacha, brzmi bardzo prosto. Mówi ona, że każdą liczbę parzystą, większą od 2, można przedstawić jako sumę dwóch liczb pierwszych. Wydaje się to prawdziwe, ale w ciągu ponad 250 lat nikomu nie udało się tego udowodnić ( może łatwiej udowodnić, że tej hipotezy nie da się udowodnić? ).
Prawdziwość hipotezy Goldbacha była już testowana w ograniczonym zakresie - bodajże do wielkości rzędu 1017. Ale być może gdzieś w bezmiarze liczb znajdzie się jakaś "czarna owca" - liczba parzysta, której nie da się uzyskać poprzez dodanie dwóch liczb pierwszych.

Widoczne jest, że generalnie im większa liczba parzysta tym większa liczba sposobów jej rozkładu na sumę dwóch liczb pierwszych.
Liczby 4, 6 i 8 można przedstawić tylko na jeden sposób: 4=2+2, 6=3+3, 8=3+5. Dla liczby 10 mamy dwie możliwości: 3+7 lub 5+5. Ilości takich możliwych rozkładów dla niektórych liczb:

100 - 6  1.000 - 28  2.000 - 37  20.000 - 231
102 - 8  1.002 - 36  2.002 - 44  20.002 - 176

A to wykres przedstawiający liczbę tych możliwości, sporządzony dla 9.999 kolejnych liczb parzystych (od 4 do 20.000). Każdej z tych liczb odpowiada jeden żółty punkt na wykresie.



A tak to wygląda dla liczb w zakresie do 100.000:


Wyglądają interesująco! Ale pozostawiam bez dodatkowych komentarzy, bo na milion dolarów też mam ochotę ...  ;)


Niektóre z informacji zaczerpnięto ze stron:
- http://primes.utm.edu/howmany.shtm (ilości liczb pierwszych dla N ≥ 1 000 000 000)
- http://www.wiw.pl/nowinki/matematyka/200008/20000809-001.asp
- http://aci.pb.bielsko.pl/~swasowicz/pierwsze.html

Jan K. Nowakowski

początek strony

stat4u