i
i
“1298-Pavlic-Porazdelitev” — 2010/7/23 — 11:30 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 24 (1996/1997)
Številka 3
Strani 140–143
Gregor Pavlič:
PORAZDELITEV PRAŠTEVIL V MNOŽICI N
Ključne besede: matematika, teorija števil, praštevila.
Elektronska verzija: http://www.presek.si/24/1298-Pavlic.pdf
c© 1996 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
1140 Mat ematika I
PORAZDELITEV PRAŠTEVIL V MNOŽICI- IN
Ena od poti ugotavlj anj a gostote prašt evilje proučevanje zaporedja znanih
pr aštevil. Ali se mord a v njem skriva kakšen vzorec?
Tako vidimo, da je med prvimi 100 naravnimi števili 25 prašt evil:
2, 3,5 ,7,11 ,13 ,17,1 9,2 3,2 9, 31,37,41 , 43,
47, 53, 59, 61, 67, 71, 73, 79,83, 89, 97,
da so še kar enakomerno porazdeljena, da se med njimi poj avljajo opazne
pr aznine, da pa je med njimi kar 8 parov oblike p , p + 2, im enovanih tudi
praštevilski dvojčki .
Med 101 in 200 j e 21 praštevil
101,103,107,109,11 3,127 ,131,137,1 39,149 ,151,
157,163,167 ,173,179,1 81,191 ,1 93,197 ,199
in med njimi 7 prašt evilsk ih dvojčkov , praznine pa so že bolj opazne. Tako
si lahko post avimo vprašanj i: ali obstaj ajo med zaporednima prašteviloma
t udi večj i skoki in ali je praštevilskih dvojčkov neskončno mn ogo. Zani-
mivo je, da je odgovor na prvo vprašanje zelo enost aven, odgovora na
drugo vprašanje pa še ni ; obst aj a le domn eva , da je odgovor pritrdilen.
Do let a 1994 največj a znana pr ašt evilska dvojčka sta 1000000000061 in
1000000000063.
Poglejmo t orej odgovor na prvo vprašanje. Najdaljši niz zap orednih
sest avlj enih št evil med prvimi 200 nar avnimi štev ili je 182,1 83, . .. 190.
Ali j e mogoče brez t ruda sestavit i še daljši tak niz , ne da bi izpopolnj evali
t ab elo pr aštevil? To j e mogoče in lahko je niz celo poljubno dolg, le da je
vsa ta števila težko izpisati , ker so zelo velika. Pri mer za niz 9 zap orednih
sestavljenih števil je
ID! + 2, ID! + 3, . .. , ID! + 10
in na splošno za niz n zaporednih sestavljenih števil
(n+l}!+ 2, (n+l}!+ 3, . . . , (n+l}!+(n+l) .
I Matematika
Ali je po ugotovitvi , da je med zaporednima prašteviloma lahko poljubno
velika "razpoka", sploh še vredno ugotavljati porazdeljenost praštevil?
Pokazali bomo, da vendarle veljajo določene zakonitosti . V ta namen defi-
nirajmo aritmetičnofunkcijo 1I"(X) , katere vrednost naj bo število praštevil,
ki so manjša ali enaka št evilu x . Očitno je 11"(100) = 25 in 11"(200) = 46.
Zakonitosti pa se pokažejo šele takrat , ko zberemo zelo veliko podatkov.
Zato si poglejmo tabelo vrednosti funkcije 11" za nekatere x do vrednosti
1010, relativne frekvence praštevil in njihove obratne vrednosti .
X 1I"(x) ~ r(x) = tr"'",
'"
10 4 0,40000000 2,50000000
100 25 0,25000000 4,00000000
1 000 168 0,16800000 5,95238095
10000 1229 0,12290000 8,13669650
100000 9592 0,09592000 10,4253545
1 000 000 78498 0,07849800 12,7391781
10000000 664579 0,06645790 15,0471201
100000000 5761455 0,05761455 17,3567267
1000000000 50847534 0,05084753 19,6666387
10000000000 455052512 0,04550525 21,9754863
V tabeli je posebej pomemben tretji stolpec, ki nam kaže "gostoto" pra-
števil.
Vzemimo prvih mil ijon naravnih števi l; med njimi je 78498 oziroma
7,85 % praštevil, večina (okrog 92 %) pa je sestavljenih števil. Iz tabele
lahko razberemo, daje ta odstotek pri prvih 10 milijonih naravnih števil še
manjši; funkcija tr~) je očitno padajoča. V tabeli pa je še četrti stolpec in
izkazalo se bo , da je funkcija r zelo pomembna. Matematiki niso obupali
pri iskanju zakonitosti v napisani tabeli, čeprav je na prvi pogled vsak
napor že vnaprej obsojen na neuspeh. Pot do rešitve se je nepričakovano
pokazala preko števila e in naravnega logaritma.
Da bi videli razvoj reševanja problema, naredim~ še eno tabelo.
x
10
100
1 000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
r(x) = .".xx
2,50000000
4,00000000
5,95238095
8,13669650
10,4253545
12,7391781
15,0471201
17,3567267
19,6666387
21,9754863
Mat ematika I
12,182494
54,598150
384,668 150
3 417,609127
33703,4168
340 843,2932
3426740,583
34508 861,36
34762633 1,2
3498101746,
Desni stolpec v tabeli sicer ne kaže neke popolne zakonitosti , vendar se
t akoj vidi , da je vsako število nižje v st olpcu približno desetkratnik pred-
hodnega višje ležečega . Opaženo dejstvo bi lahko opisali z izrazom
er( 10x) R:J 10 er (x) za velike x (1)
ali z besedami : če spremenlj ivko povečamo od x na 10x , je vrednost funk-
cije er( 10x) pri povečani neodvisni spremenIj ivki x pr ibližno desekratnik
vrednost i funk cije er(x) pri prvotni spremenIj ivki x. V tem spoznanju je
pot do rešit ve. Zakoni tost sicer ne velja za vsako funk cijo r(x), če pa
najdemo tako, da zanjo ena kost velja, smo že blizu rešitve.
Izkazalo se je, da je iskan a funkcija ravno logari temska funkcija z
osnovo e. Potrebovali bomo identi teti
V (1) nad om estimo funk cijo r(x ) z logaritemsko funkcijo ln x
e 1n( l Ox) = 10 e ln x
in prirnerjajmo oba izraza
er (10x ) R:J 10 e' ·(x), e1n (10x ) = 10 e1n x .
Takoj lahko ugotovimo, da st a ena kost i približno ena kovredni za dovolj
velike vrednosti neodvisne spremelj ivke x. Ta ugotovitev pa je ena od
oblik znam enitega prašt evilskega izreka:
Mat ematika
Razmerje m ed številom praštevil, manjših ali enakih narav-
nemu številu n , in t em naravnim številom n , ozir om a gostota
praštevil v množici naravnih števil, j e za velike n približno en a ka
ob r a t n i v red n ost i naravnega logaritma števil a n .
S tem seveda slav nega izreka nism o dokazali, sm o pa na dokaj eno-
staven način našli kar natančno aproksimacijsko funk cijo, saj se št evilo
1 d dn osti f kcii rr( 10 0 00 000 000 ) likui 1ln 10 000 00 0 000 O prave vre nosti un c ije 10000 000000 raz 1 uje e
za 0,002.
Najbolj nenavadno za to "izpeljavo" pa je, da so našli med zapiski
15-letnega Carla Fridericha Gaussa iz leta 1792 naslednji zapis:
praštevila pod a (= oo) 1: .
Če besedilo "praštevila pod a" nadomesti mo z ekvivalent no vrednost jo
7l"( a ) , zna k la z In a in (= oo) z besedilom za velike a , dobimo ravno
a
7l"(a) ;::j -1- za velike a,
na
z deljenjem z a pa obliko prašt evilskega izreka, ki smo jo "izpelj ali" .
Očitno j e ml adostnik Gauss že razum el to lastnost praštevi l, zakaj pa
je ni razvil in tudi ne dokaza l, najverjet neje ne bomo nikoli izvedeli.
Dru gi resni poskus, da bi ugotovil število praštevil , manjših od da-
nega nar avnega števila n, j e s št udijem ar i tmetične funkcije 7l"(n) naredil
fran coski matem atik Legendre leta 1808. Pri delu si je pom agal z Era-
tostenovim sitom . Kasn eje so se s tem pro blemom močno ukvarj ali še
Čebišev , Riemann , Mert ens in Sylvest er . Šele let a 1896 st a praštevilski
izrek neodvisno dokazala J acques Had amard (1865-1963) in C. J. de la
Vallee Poussin (1866-1962). Pri tem sta uporabil a Riem annovo zeta funk-
cijo in dosežke mn ogih svoj ih predhodnikov v analitičn i teo riji štev il.
Dolgo časa so bili matem at iki prepričan i , da se pri dokazovanju teg a
izreka ne da izogni t i analitičn im metodam , zato je bil elementarn i dokaz ,
ki sta ga leta 1949 objavila P. Erdos in A. Selberg, prava senzacija. Alte
Selberg je bil zato nagr aj en s Fieldsovo medalj o - na grado, ki je po po-
membnosti enakovredna Nobelovi nagradi , Paul Erdos pa je dobil Coleovo
nagrado.
Gregor Pavlič