Pr´ımsz´amok statisztikai anal´ızise Puszta Adri´an 2008. ´aprilis 18.
Kivonat Munk´am sor´an a pr´ımsz´amok ´es a p´aros pr´ımek eloszl´as´at, illetve k¨ ul¨onbs´eg´et vizsg´altam, majd ebb˝ol k¨ovetkeztettem a v´eletlenszer˝ u eloszl´as megl´et´ere.
1.
Elm´ eleti ´ attekint´ es
A Wikip´edia [1] szerint egy p sz´amot akkor nevez¨ unk pr´ımnek, ha abb´ol, hogy p oszt´oja a · b-nek, k¨ovetkezik, hogy p oszt´oja vagy a-nak, vagy b-nek. M´ar Euklidesz is adott egy bizony´ıt´ast [2] arra, hogy v´egtelen sok pr´ımsz´am van. A pr´ımek darabsz´am´at x -ig a k¨ovetkez˝ o formul´aval k¨ozel´ıthetj¨ uk:
Li(x) =
Z
0
x
1 dt log t
(1)
Az (1) egyenlet illeszked´es´et nem fogom ellen˝orizni. P´aros- vagy ikerpr´ımeknek azokat a pr´ım p´arokat nevezz¨ uk, melyeknek k¨ ul¨onbs´ege kett˝ o. Ezekre a sz´amokra van egy sejt´es, miszerint v´egtelen sokan vannak. Ezt m´aig nem siker¨ ult bizony´ıtani, de a matematikusok todtak korl´atot adni egy adott x -ig az ikerpr´ımek darabsz´am´ara. A jelenleg ismert legnagyobb ikerpr´ım p´ar 58711 sz´amjegyb´ol ´all.
2.
Gyakorlati megval´ os´ıt´ as
Eszk¨ oz¨ ok A feladat elv´egz´es´ehez awk ´es C++ programokat haszn´altam a sz´amol´asokhoz, ´es az eredm´enyeket Gnuplottal ´abr´azoltam. Az ´abr´azol´ashoz scripteket ´ırtam, hogy meg tudjam ism´etelni a rajzot.
1
2.1.
Pr´ımek vizsg´ alata
A primes.txt file-ban 2-t˝ ol kb. 1.7 milli´oig vannak benne a pr´ımek. Egy egyszer˝ u awk program seg´ıts´eg´evel sorsz´amot is tudtam rendelni a pr´ımekhez. Az 1. ´abr´an ezekre az adatokra egyenest illesztettem, ez az ´abr´azolt tartom´anyon el´eg j´ol illeszkedik. K´et pr´ım t´avols´ag´at a dvsn.awk programmal sz´amoltattam ki, ami ki´ırja a sz´amot, az el˝ otte l´ev˝ o pr´ımhez k´epesti t´avols´ag´at, ´es a sorsz´amot is. A 2. ´abr´at csup´an illusztr´aci´onak sz´anom, hogy megmutassam, mennyire ”ugr´al” a t´avols´ag a pr´ımek f¨ uggv´eny´eben. A k¨ ul¨onbs´egeket tartalmaz´o file-okb´ol a histo.awk programmal hisztogramot k´esz´ıtettem. A hisztogrammot el˝osz¨or 2. pr´ımt˝ol a 10000.-ig csin´altam meg (3. ´abra), ut´ana 10000.-t˝ol 20000.-ig (4. ´abra), v´eg¨ ul a 90000.-t˝ol a 100000.-ig. Az adatokra exponenci´alis g¨orb´et illesztettem (5. ´abra). Ez mindh´arom adatsor eset´en el´eg j´o illeszt´es. Az ´atlagos t´avols´agokat is kisz´amoltam, egy sz´amhoz hozz´arendeltem a t˝ole jobbra ´es balra l´ev˝ o 5. pr´ımek k¨ ul¨onbs´eg´enek tized´et. Ezt felrajzolva kaptam a 6. ´abr´at. Erre az adatsorra is megcsin´altam s hisztogrammot (7. ´abra).
2.2.
P´ aros pr´ımek (ikerpr´ımek) vizsg´ alata
A p´aros pr´ımeket nagyon egyszer˝ u volt megtal´alni, hiszen azokat az elemeket kellett megkeresni, melyeknek 2 a t´avols´aga az el˝ oz˝ot˝ol. A 8. ´abra nem mutat u ´jdons´agot az 1. ´abr´ahoz k´epest, mivel a p´aros pr´ımek halmaza r´eszhalmaza a pr´ımek halmaz´anak. Ez´ert egyenest illesztve az adatokra szint´en j´o egyez´est kapunk. Szint´en ´abr´azoltam a k¨ ul¨onbs´egeket a 9. ´abr´an. A t´avols´agok eloszl´as´at megcsin´alva nagyon sz´ep exponenci´alist kapunk (10. ´abra). Itt is kisz´amoltam az ´atlagos t´avols´agot (11. a´bra), ´es az ehhez tartoz´o hisztogrammot is (12. ´abra).
Egy ´ erdekess´ eg Ebben az esetben a c´elom az volt, hogy a pr´ımeket ”feltekerjem” egy spir´alra, vagyis hozz´ajuk rendeljek egy (r, ϕ) sz´amp´art. Mivel a param´etereket nem tudtam u ´gy be´all´ıtani, mint Sacks1 , ´ıgy nem siker¨ ult olyan k´epet kapnom, amiben fel lehetne fedezni valamilyen strukt´ ur´at. A pr´ımekb˝ol a spiral.cpp C++ program csin´alt (r, ϕ) p´arokat, el˝ ozetes matematikai sz´amol´asok alapj´an. Az eredm´eny Guplottal ´abe´azoltam pol´arkoordin´ata rendszerben. A v´egeredm´eny a 13. ´arb´an l´athat´o. 1
http://hu.wikipedia.org/wiki/Sacks-spir%C3%A1l
2
3.
´ Ertelmez´ es
A t´avols´agok eloszl´as´anak exponenci´alis jellege arra utal, hogy a pr´ımek, ill. a p´aros pr´ımek v´eletlenszer˝ uen oszlanak el a sz´amegyenesen. A v´eletlenszer˝ u eloszl´as m´asik bizony´ıt´eka az ´atlagos t´avols´agok eloszl´asa. A centr´alis hat´areloszl´ast´etel szerint min´el t¨obb v´eletlen v´altoz´ot adunk ¨ossze, azoknak az eloszl´asa egyre ink´abb a Gauss-g¨orb´ehez fog tartani. Mivel mindk´et esetben az ´atlagos t´avols´agok eloszl´as´ara egy Gauss-g¨orb´ehez hasonl´o pontfelh˝ot kaptam, j´o es´ellyel tekintet˝ ok a t´avols´agok v´eletlenszer˝ unek.
Hivatkoz´ asok [1] http://hu.wikipedia.org/wiki/Pr%C3%ADmsz%C3%A1mok [2] http://primes.utm.edu/notes/proofs/infinite/euclids.html
3
Primek sorszama a szam fuggvenyeben 140000 Jelmagyarazat sorszam a*x+b 120000 a = 0.0743 b = 3500.0001
sorszam
100000
80000
60000
40000
20000
0 0
200000
400000
600000
800000
1e+06
1.2e+06
1.4e+06
1.6e+06
1.8e+06
prim
1. ´abra. Sorsz´am a sz´am f¨ uggv´eny´eben
Az egymas utani primszamok kulonbsege 40 Jelmagyarazat kulonbsegek 35
30
kulonbseg
25
20
15
10
5
0 0
2000
4000
6000
8000
primszam
2. ´abra. Egym´as ut´ani pr´ımek t´avols´aga
4
10000
Az egymas utani primszamok kulonbsegenek gyakorisaga 2500 Jelmagyarazat kulonbsegek -b*x a*e a = 1954.7309 b = 0.0838
2000
gyakorisag
1500
1000
500
0 0
6
12
18
24
30 kulonbsegek
36
42
48
54
60
3. ´abra. 1.-t˝ol 10000.-ig l´ev˝ o egym´as ut´ani pr´ımek t´avols´ag´anak eloszl´asa
Az egymas utani primszamok kulonbsegenek gyakorisaga 1800 Jelmagyarazat kulonbsegek -b*x a*e
1600
a = 1681.9133
1400
b = 0.0731
gyakorisag
1200 1000 800 600 400 200 0 0
6
12
18
24
30 kulonbsegek
36
42
48
54
60
4. ´abra. 10000.-t˝ol a 20000.-ig l´ev˝ o egym´as ut´ani pr´ımek t´avols´ag´anak eloszl´asa
5
Az egymas utani primszamok kulonbsegenek gyakorisaga 1600 Jelmagyarazat kulonbsegek -b*x a*e
1400
a = 1435.7361 b = 0.0634 1200
gyakorisag
1000
800
600
400
200
0 0
6
12
18
24
30 kulonbsegek
36
42
48
54
60
5. ´abra. 90000.-t˝ol a 100000.-ig l´ev˝ o egym´as ut´ani pr´ımek t´avols´ag´anak eloszl´asa
Atlagos tavolsag 35 Jelmagyarazat atlag tav 30
atlag tav
25
20
15
10
5
0 0
20000
40000
60000
80000
100000
primek
6. ´abra. Pr´ımek ´atlagos t´avols´aga
6
120000
140000
Atlagos tavolsag gyakorisaga a szam fuggvenyeben 6000 Jelmagyarazat atlag tav
atlag tav. gyakorisaga
5000
4000
3000
2000
1000
0 5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
prim
7. ´abra. Pr´ımek ´atlagos t´avols´aga
Paros primek sorszama a szam fuggvenyeben 80000 Jelmagyarazat kulonbsegek a*x+b
70000
a = 0.0754 b = 3499.9977 60000
sorszam
50000
40000
30000
20000
10000
0 0
200000
400000
600000
800000
paros prim
8. ´abra. P´aros pr´ımek a sorsz´amok f¨ uggv´eny´eben
7
1e+06
Az egymas utani ikerprimek kulonbsege 250 Jelmagyarazat kulonbsegek
200
kulonbseg
150
100
50
0 0
2000
4000
6000
8000
10000
primszam
9. ´abra. Egym´as ut´ani p´aros pr´ımek t´avols´aga
Az egymas utani paros primszamok kulonbsegenek relativ gyakorisaga 0.14 Jelmagyarazat kulonbsegek -b*x a*e 0.12 a = 0.1250 b = 0.1084
relativ gyakorisag
0.1
0.08
0.06
0.04
0.02
0 0
10
20
30 kulonbsegek
40
50
10. ´abra. Egym´as ut´ani p´aros pr´ımek t´avols´ag´anak eloszl´asa
8
60
Atlagos tavolsag 350 Jelmagyarazat atlag tav 300
atlag tav
250
200
150
100
50
0 0
2000
4000
6000
8000
10000
12000
14000
paros prim
11. ´abra. P´aros pr´ımek ´atlagos t´avols´aga
Atlagos tavolsag gyakorisaga a szam fuggvenyeben 180 Jelmagyarazat atlag tav 160
atlag tav. gyakorisaga
140 120 100 80 60 40 20 0 50
100
150 prim
200
250
12. ´abra. P´aros pr´ımek ´atlagos t´avols´ag´anak eloszl´ asa
9
300
1000 "r_fi.dat" u 1:2 800 600 400 200 0 200 400 600 800 1000 1000
800
600
400
200
0
200
400
13. ´abra. A pr´ımek spir´alra feltekerve
10
600
800
1000
