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.229
12,29
1.229
12,29
11,74
10.001 - 20.000
1.033
10,33
2.262
11,31
10,40
20.001 - 30.000
983
9,83
3.245
10,82
9,87
30.001 - 40.000
958
9,58
4.203
10,51
9,56
40.001 - 50.000
930
9,30
5.133
10,27
9,33
50.001 - 60.000
924
9,24
6.057
10,10
9,16
60.001 - 70.000
878
8,78
6.935
9,91
9,02
70.001 - 80.000
902
9,02
7.837
9,80
8,91
80.001 - 90.000
876
8,76
8.713
9,68
8,81
90.001 - 100.000
879
8,79
9.592
9,59
8,72
...
...
...
...
...
...
19.990.001 - 20.000.000
596
5,96
1.270.617
6,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)
N
Rzeczywista ilość liczb pierwszych
Ilość LP wg całki
Odchylenie %
10
4
6
50,0
50
15
18
20,0
100
25
30
20,0
500
95
102
7,4
1.000
168
177
5,4
2.000
303
315
4,3
3.000
430
443
3,0
4.000
550
565
2,7
5.000
669
684
2,2
10.000
1.229
1.246
1,4
50.000
5.133
5.166
0,6
100.000
9.592
9.629
0,4
500.000
41.538
41.606
0,16
1.000.000
78.498
78.627
0,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:
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/
N
Rzeczywista ilość liczb pierwszych
Pełna wartość całki
Wartość do wyrazu numer k
Wartość
Odchylenie %
k
Wartość
Odchylenie %
100
25
30
+20,0
5
25
0,00
1.000
168
177
+5,36
10
169
+0,60
10.000
1.229
1.246
+1,38
15
1.230
+0,08
100.000
9.592
9.629
+0,39
20
9.595
+0,03
1.000.000
78.498
78.627
+0,16
25
78.545
+0,06
10.000.000
664.579
664.918
+0,05
30
664.718
+0,02
100.000.000
5.761.455
5.762.209
+0,01
35
5.761.704
+0,004
1.000.000.000
50.847.534
50.849.234
+0,003
40
50.847.930
+0,0008
10.000.000.000
455.052.511
455.055.614
+0,0007
45
455.052.183
-0,0001
100.000.000.000
4.118.054.813
4.118.066.410
+0,0003
50
4.118.057.242
+0,0001
1.000.000.000.000
37.607.912.018
37.607.951.903
+0,0001
55
37.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.
N
Rzeczywista 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ść LP
Odch. %
Ilość LP
Odch. %
Ilość LP
Odch. %
Ilość LP
Odch. %
10.000
1.229
1.086
-11,66
1.218
-0,90
1.231
+0,12
1.229
0,00
100.000
9.592
8.686
-9,45
9.512
-0,83
9.588
-0,04
9.579
-0,14
1.000.000
78.498
72.382
-7,79
78.030
-0,60
78.543
+0,06
78.480
-0,02
10.000.000
664.579
620.421
-6,64
661.459
-0,47
665.140
+0,08
664.686
+0,02
100.000.000
5.761.455
5.428.681
-5,78
5.740.304
-0,37
5.768.004
+0,11
5.764.595
+0,05
1.000.000.000
50.847.534
48.254.942
-5,10
50.701.542
-0,29
50.917.519
+0,14
50.890.952
+0,09
10.000.000.000
455.052.511
434.294.482
-4,56
454.011.971
-0,23
455.743.004
+0,15
455.530.157
+0,10
100.000.000.000
4.118.054.813
3.948.131.654
-4,13
4.110.416.301
-0,19
4.124.599.869
+0,16
4.122.856.417
+0,12
1.000.000.000.000
37.607.912.018
36.191.206.825
-3,77
37.550.193.650
-0,15
37.668.527.415
+0,16
37.653.985.575
+0,12
10.000.000.000.000
346.065.536.839
334.072.678.387
-3,47
345.618.860.221
-0,13
346.621.096.885
+0,16
346.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:
N
Rzeczywista ilość liczb pierwszych
Ilość LP uzyskana wg wzoru
Odchylenie od rzecz. ilości %
10.000
1.229
1.229
0,00
100.000
9.592
9.586
-0,067
1.000.000
78.498
78.498
0,00
10.000.000
664.579
664.555
-0,004
100.000.000
5.761.455
5.761.584
+0,002
1.000.000.000
50.847.534
50.851.640
+0,008
10.000.000.000
455.052.511
455.088.177
+0,008
100.000.000.000
4.118.054.813
4.118.195.721
+0,003
1.000.000.000.000
37.607.912.018
37.606.434.721
-0,004
10.000.000.000.000
346.065.536.839
346.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 7.01.2016r. odkryta została 49. wielka liczba pierwsza Mersenne'a: 274.207.281 - 1. Liczba ta ma 22.338.618 cyfr. Poprzednia 48. liczba (257.885.161 - 1 ; 17.425.170 cyfr) odkryta była w 2013 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.
n
Legendre
Euler
n2 - 3n + 43
n2 - 5n + 47
n2 - 81n + 1681
2n2 - 116n + 1711
3n2 - 135n + 1541
4n2 - 166n + 1763
6n2 - 354n + 5251
9n2 - 249n + 1763
2n2 + 29
n2 - n + 41
n2 - 79n +1601
Ogółem LP:
28
40
79
41
42
80
57
44
40
58
40
Unikalnych LP:
28
40
40
40
40
40
29
22
40
29
40
1
31
41
1.523
41
43
1.601
1.597
1.409
1.601
4.903
1.523
2
37
43
1.447
41
41
1.523
1.487
1.283
1.447
4.567
1.301
3
47
47
1.373
43
41
1.447
1.381
1.163
1.301
4.243
1.097
4
61
53
1.301
47
43
1.373
1.279
1.049
1.163
3.931
911
5
79
61
1.231
53
47
1.301
1.181
941
1.033
3.631
743
6
101
71
1.163
61
53
1.231
1.087
839
911
3.343
593
7
127
83
1.097
71
61
1.163
997
743
797
3.067
461
8
157
97
1.033
83
71
1.097
911
653
691
2.803
347
9
191
113
971
97
83
1.033
829
569
593
2.551
251
10
229
131
911
113
97
971
751
491
503
2.311
173
11
271
151
853
131
113
911
677
419
421
2.083
113
12
317
173
797
151
131
853
607
353
347
1.867
71
13
367
197
743
173
151
797
541
293
281
1.663
47
14
421
223
691
197
173
743
479
239
223
1.471
41
15
479
251
641
223
197
691
421
191
173
1.291
53
16
541
281
593
251
223
641
367
149
131
1.123
83
17
607
313
547
281
251
593
317
113
97
967
131
18
677
347
503
313
281
547
271
83
71
823
197
19
751
383
461
347
313
503
229
59
53
691
281
20
829
421
421
383
347
461
191
41
43
571
383
21
911
461
383
421
383
421
157
29
41
463
503
22
997
503
347
461
421
383
127
23
47
367
641
23
1.087
547
313
503
461
347
101
23
61
283
797
24
1.181
593
281
547
503
313
79
29
83
211
971
25
1.279
641
251
593
547
281
61
41
113
151
1.163
26
1.381
691
223
641
593
251
47
59
151
103
1.373
27
1.487
743
197
691
641
223
37
83
197
67
1.601
28
1.597
797
173
743
691
197
31
113
251
43
1.847
29
853
151
797
743
173
29
149
313
31
2.111
30
911
131
853
797
151
31
191
383
31
2.393
31
971
113
911
853
131
37
239
461
43
2.693
32
1.033
97
971
911
113
47
293
547
67
3.011
33
1.097
83
1.033
971
97
61
353
641
103
3.347
34
1.163
71
1.097
1.033
83
79
419
743
151
3.701
35
1.231
61
1.163
1.097
71
101
491
853
211
4.073
36
1.301
53
1.231
1.163
61
127
569
971
283
4.463
37
1.373
47
1.301
1.231
53
157
653
1.097
367
4.871
38
1.447
43
1.373
1.301
47
191
743
1.231
463
5.297
39
1.523
41
1.447
1.373
43
229
839
1.373
571
5.741
40
1.601
41
1.523
1.447
41
271
941
1.523
691
6.203
41
43
1.601
1.523
41
317
1.049
823
42
47
1.601
43
367
1.163
967
43
53
47
421
1.283
1.123
44
61
53
479
1.409
1.291
45
71
61
541
1.471
46
83
71
607
1.663
47
97
83
677
1.867
48
113
97
751
2.083
49
131
113
829
2.311
50
151
131
911
2.551
51
173
151
997
2.803
52
197
173
1.087
3.067
53
223
197
1.181
3.343
54
251
223
1.279
3.631
55
281
251
1.381
3.931
56
313
281
1.487
4.243
57
347
313
1.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ę ... ;)
