i
i
“Bracic” — 2019/6/26 — 8:14 — page 1 — #1 i
i
i
i
i
i
GENERATORJI PRAŠTEVIL
JANKO BRAČIČ
Naravoslovnotehnǐska fakulteta
Univerza v Ljubljani
Math. Subj. Class. (2010): 11A41
Generator praštevil je postopek, ki nam na vsakem koraku vrne praštevilo oziroma
množico praštevil. V članku predstavimo nekaj znanih in manj znanih generatorjev pra-
števil.
PRIME NUMBER GENERATORS
A prime generator is an algorithm which on each step returns a prime number or a set
of prime numbers. In this paper we present some known and less known prime generators.
Uvod
Množica naravnih števil N ima po eni strani preprosto strukturo, ki se na-
naša na seštevanje. Do vsakega naravnega števila pridemo z enostavnim
postopkom: začnemo s številom 1, prǐstejemo 1 in dobimo 2, spet prǐste-
jemo 1 in dobimo 3 itd. Rečemo lahko, da ima aditivna struktura v N en
sam osnovni gradnik, število 1. Tesno povezana z aditivno strukturo v N je
dobra urejenost te množice.
Po drugi strani je multiplikativna struktura množice N manj enostavna.
Potrebujemo veliko osnovnih gradnikov – praštevil, da lahko vsako naravno
število izrazimo kot njihov produkt. Že starogrški matematiki so vedeli, da
za vsako naravno število n ≥ 2 obstajajo takšna enolično določena praštevila
p1 < · · · < pk in naravna števila e1, . . . , ek, da je n = pe11 · · · p
ek
k . Na tem
osnovnem izreku aritmetike sloni Evklidov dokaz, da je praštevil neskončno
mnogo. Idejo njegovega dokaza lahko uporabimo za konstrukcijo generatorja
praštevil. Z generatorjem praštevil imamo v mislih postopek, ki nam ob
ustreznih začetnih podatkih da eno ali več praštevil. Iz Evklidovega dokaza
lahko izluščimo naslednji postopek za generiranje praštevil.
Obzornik mat. fiz. 66 (2019) 1 1
i
i
“Bracic” — 2019/6/26 — 8:14 — page 2 — #2 i
i
i
i
i
i
Janko Bračič
• Naj bo {q1, . . . , ql} poljubna množica praštevil;
• produktu q1 · · · ql prǐstejemo 1, da dobimo število n = q1 · · · ql + 1 > 2;
• osnovni izrek aritmetike zagotavlja obstoj takšnih enolično določenih
praštevil p1 < · · · < pk in naravnih števil e1, . . . , ek, da je n = pe11 · · · p
ek
k ;
• dobili smo množico praštevil {p1, . . . , pk} in vsako od njih je različno
od praštevil v začetni množici.
Ker je {q1, . . . , ql} prava podmnožica v {q1, . . . , ql, p1, . . . , pk}, lahko skle-
pamo, da je praštevil neskončno mnogo.
K pravkar opisanemu generatorju praštevil se bomo vrnili pozneje, ko
bomo govorili o njegovih variantah, celi družini generatorjev praštevil, ki
jim rečemo evklidski generatorji praštevil.
Obrazci za računanje praštevil
Že Euler je opazil, da je vrednost polinoma f(n) = n2 + n + 41 praštevilo
za vse n = 0, 1, . . . , 39. Ker je f(40) = 1681 = 412, ta kvadratni polinom
ni generator praštevil. Seveda lahko z interpolacijo za vsak nabor praštevil
p1, . . . , pk najdemo takšen polinom f , da je f(n) = pn za vse n = 1, . . . , k.
Na žalost pa pri interpolaciji stopnja polinoma f narašča s k. Green in Tao
[5] sta dokazala zelo globok izrek o praštevilih. Pokazala sta, da so v mno-
žici praštevil poljubno dolga aritmetična zaporedja. Z drugimi besedami,
za vsako naravno število k obstajata takšni naravni števili uk, vk, da je vre-
dnost linearne funkcije l(n) = ukn + vk praštevilo za vse n = 1, 2, . . . , k.
Števili uk in vk sta si seveda tuji, zato je po Dirichletovem izreku o pra-
številih v aritmetičnem zaporedju l(n) neskončno mnogo praštevil. A že
zelo enostaven argument nas prepriča, da l(n) ne more biti praštevilo za vse
n ∈ N. Namreč, za n = uk + vk + 1 je l(n) = (uk + 1)(uk + vk). Prav-
zaprav ni takšnega nekonstantnega polinoma f , katerega vrednost f(n) bi
bila praštevilo za vsako naravno število n. Dokažemo lahko še več.
2 Obzornik mat. fiz. 66 (2019) 1
i
i
“Bracic” — 2019/6/26 — 8:14 — page 3 — #3 i
i
i
i
i
i
Generatorji praštevil
Trditev 1. Ne obstaja takšen nekonstanten polinom f , katerega vrednosti
f(n) so praštevila za vsa naravna števila n iz nekega aritmetičnega zaporedja
naravnih števil.
Dokaz. Ideja dokaza je iz [6]. Vzemimo, da obstajata takšen nekonstanten
polinom f in takšno aritmetično zaporedje A = {dk + e; k = 0, 1, 2 . . .},
da je f(n) praštevilo za vse n ∈ A. Potem je f(e) = p praštevilo. Ker je
dpj + e ∈ A za vse j ∈ N, je tudi vsako od števil f(dpj + e) praštevilo. Iz
dpj+e ≡ e (mod p) sledi (dpj+e)m ≡ em (mod p) za vsako naravno število
m, kar nam da f(dpj + e) ≡ f(e) ≡ 0 (mod p) za vse j ∈ N. To pomeni,
da je praštevilo f(dpj + e) enako p. Toda to je nemogoče, saj nekonstanten
polinom ne more zavzeti iste vrednosti neskončnokrat.
Zdaj, ko vemo, da ni takšnega polinoma f , pri katerem bi bilo f(n)
praštevilo za vsa števila n iz nekega aritmetičnega zaporedja naravnih števil,
se postavlja vprašanje, ali sploh obstaja takšna nekonstantna funkcija f ,
katere vrednosti f(n) so praštevila za vse n iz neke neskončne množice
naravnih števil. Preden odgovorimo na to vprašanje, dokažimo naslednjo
trditev.
Lema 2. Naravno število n 6= 4 je praštevilo natanko tedaj, ko n ne deli
števila (n− 1)!.
Dokaz. Če je n praštevilo, potem število (n − 1)! ni deljivo z n. Za dokaz
obrata moramo pokazati, da vsako naravno število n 6= 4, ki ni praštevilo,
deli število (n − 1)!. Ker za n = 1 to očitno velja, lahko predpostavimo,
da je n sestavljeno število. Vzemimo najprej, da obstaja razcep n = uv,
kjer sta 1 < u < v < n. Potem seveda u in v nastopata v produktu
(n − 1)! = 1 · 2 · · ·u · · · v · · · (n − 1) in zato n|(n − 1)!. Razcep n = uv z
1 < u < v < n obstaja za vsako sestavljeno število n, razen za števila
oblike n = p2, kjer je p praštevilo. Predpostavimo torej, da je n = p2
za neko praštevilo p. Ker je n 6= 4, je p liho praštevilo. Iz (p2 − 1)! =
1 · 2 · · · p · (p+ 1) · · · (2p) · (2p+ 1) · · · (p2 − 1) vidimo, da p2|(p2 − 1)!.
1–10 3
i
i
“Bracic” — 2019/6/26 — 8:14 — page 4 — #4 i
i
i
i
i
i
Janko Bračič
Za realno število x označimo z bxc največje celo število, ki ne presega x,
in z dxe najmanǰse celo število, ki ga x ne presega. Na primer, b2,4c = 2 in
d2,4e = 3. Če je x celo število, potem je bxc = dxe = x.
Poglejmo zdaj funkcijo
f(n) =
⌈
2(n− 1)!
n
−
⌊
2(n− 1)!
n
⌋⌉
(n− 2) + 2.
Izračunamo lahko, da je f(1) = 2, f(2) = 2, f(3) = 3, f(4) = 2, f(5) = 5,
f(6) = 2 itd.
Trditev 3. Funkcija f je generator praštevil. Če je n praštevilo, je f(n) =
n, za druga naravna števila n pa je f(n) = 2.
Dokaz. Če je n liho praštevilo, potem po lemi 2 število 2(n−1)!n ni celo, kar po-
meni, da je 2(n−1)!n −
⌊
2(n−1)!
n
⌋
število z intervala (0, 1) in zato⌈
2(n−1)!
n −
⌊
2(n−1)!
n
⌋⌉
= 1. Ker že vemo, da je f(2) = 2, lahko zaključimo, da
je f(n) = n, če je n praštevilo. Po drugi strani, če je n 6= 4 sestavljeno število
ali enako 1, je po lemi 2 2(n−1)!n celo število in zato
2(n−1)!
n −
⌊
2(n−1)!
n
⌋
= 0.
Ker je f(4) = 2, vidimo, da je f(n) = 2, če n ni praštevilo.
Naša konstrukcija funkcije f iz trditve 3 temelji na funkciji, ki je pred-
stavljena na spletni strani [10].
Bertrandov postulat (včasih imenovan tudi izrek Bertrand-Čebǐseva)
pravi, da za vsako število x > 1 obstaja na intervalu [x, 2x] vsaj eno prašte-
vilo. Odkar je leta 1852 Čebǐsev dokazal ta izrek, so ga matematiki precej
izbolǰsali. Tako so, na primer, leta 2001 Baker, Harman in Pintz v članku
[1] pokazali, da obstaja takšno število x0 > 0, da za vsak x ≥ x0 interval
[x, x + x21/40] vsebuje vsaj eno praštevilo. Avtorji v svojem članku trdijo,
da je mogoče število x0 efektivno izračunati, a ne navajajo nobene ocene za
velikost števila x0.
Označimo s pn n-to praštevilo. Torej, p1 = 2, p2 = 3, p3 = 5 itd. Iz
rezultata, ki so ga dokazali Baker, Harman in Pintz, sledi, da obstaja takšen
4 Obzornik mat. fiz. 66 (2019) 1
i
i
“Bracic” — 2019/6/26 — 8:14 — page 5 — #5 i
i
i
i
i
i
Generatorji praštevil
indeks n0, da je
pn < pn+1 < pn + p
21/40
n < pn + p
2/3
n za vse n ≥ n0.
Lema 4 ([7]). Če je N takšno naravno število, za katerega velja pn0 < N
3,
potem obstaja takšno praštevilo q, da je N3 < q < (N + 1)3 − 1.
Dokaz. Naj bo pn največje praštevilo, za katerega velja pn < N
3. Potem je
n ≥ n0 in torej velja N3 < pn+1 < pn + p2/3n < N3 +N2 < (N + 1)3 − 1.
Cheng [4] je pokazal, da lema 4 velja za vsako število N > ee
15
. Se pravi,
da lahko za pn0 vzamemo najmanǰse praštevilo, ki presega e
3e15 .
Naj bo zdaj q0 > e
3e15 poljubno praštevilo. S pomočjo leme 4 lahko
dobimo neskončno zaporedje praštevil q0 < q1 < q2 < . . ., za katerega velja
q3n < qn+1 < (qn + 1)
3 − 1 (n ∈ N).
Definirajmo zaporedji
un = q
3−n
n in vn = (qn + 1)
3−n (n ∈ N).
Lema 5 ([7]). Zaporedje un je monotono naraščajoče, zaporedje vn je mo-
notono padajoče in pri vsakem n je un < vn.
Dokaz. Očitno je un < vn. Pri vsakem n velja un+1 = q
3−n−1
n+1 > (q
3
n)
3−n−1 =
q3
−n
n = un in vn+1 = (qn+1+1)
3−n−1 < ((qn+1)
3−1+1)3−n−1 = (qn+1)3
−n
=
vn.
Trditev 6 ([7]). Obstaja takšno število α > 1, da je funkcija
g(n) =
⌊
α3
n⌋
(n ∈ N)
generator praštevil.
1–10 5
i
i
“Bracic” — 2019/6/26 — 8:14 — page 6 — #6 i
i
i
i
i
i
Janko Bračič
Dokaz. Naj bosta un in vn zaporedji, ki smo ju definirali prej. Ker je zapo-
redje un monotono naraščajoče in navzgor omejeno, je konvergentno. Naj
bo α = lim
n→∞
un. Ker je vn monotono padajoče zaporedje in velja un < vn,
je un < α < vn za vse n ∈ N. Od tod sledi qn = u3
n
n < α
3n < v3
n
n = qn + 1
za vse n ∈ N. Torej je
⌊
α3
n⌋
= qn.
Obe funkciji, ki smo ju predstavili v tem razdelku, imata le teoretični
pomen, za konkretno generiranje praštevil nista uporabni. Bolj ali manj
je tako z vsemi funkcijami, ki generirajo praštevila. Funkcija f iz trditve
3 zahteva veliko računskih operacij za izračun vrednosti f(n). Funkcija g
iz trditve 6 pa ima to dodatno pomanjkljivost, da števila α ne poznamo,
saj je definirano kot limita. V naslednjem razdelku bomo zato pogledali
generatorje praštevil, ki so bolj priročni.
Sita
Sito je postopek, ki v dani neprazni končni množici naravnih števil poǐsče
vsa praštevila. Najbolj znano je Eratostenovo sito. Postopek je naslednji.
Naj bo M končna neprazna množica naravnih števil in naj bo m največje
število v M . Množico M presejemo takole:
• naj bo M1 = M \ {1};
• za vsak n = 2, . . . , b
√
mc, naj bo Mn = Mn−1 \ {kn; k = 2, . . . , bmn c}.
Ko je postopek končan, dobimo množico Mb
√
mc, v kateri so natanko vsa
praštevila iz množice M . Verjetno tega ni treba dokazovati, saj je Eratoste-
novo sito zelo znan generator praštevil.
Indijski matematik Sundaram je leta 1934 odkril zelo zanimivo sito.
Naša predstavitev tega sita temelji na [11]. Začnimo z naslednjo tabelo
6 Obzornik mat. fiz. 66 (2019) 1
i
i
“Bracic” — 2019/6/26 — 8:14 — page 7 — #7 i
i
i
i
i
i
Generatorji praštevil
naravnih števil.
4 7 10 13 16 19 22 25 . . .
7 12 17 22 27 32 37 42 . . .
10 17 24 31 38 45 52 59 . . .
13 22 31 40 49 58 67 76 . . .
16 27 38 49 60 71 82 93 . . .
...
...
...
...
...
...
...
...
(1)
Kaj je na tej tabeli zanimivega? Vidimo, da je v vsaki vrstici in vsakem
stolpcu aritmetično zaporedje števil. V prvem stolpcu je v j-ti vrstici število
4 + 3(j − 1) = 3j + 1. To je prvi člen aritmetičnega zaporedja v j-ti vrstici.
Razlika aritmetičnega zaporedja v j-ti vrstici je liho število 2j+1. Se pravi,
da je v j-ti vrstici in k-tem stolpcu število 3j+1+(k−1)(2j+1) = 2jk+j+k.
Zdaj lahko razkrijemo najbolj zanimivo lastnost tabele (1).
Trditev 7. Liho število 2n + 1 je praštevilo natanko tedaj, če število n ni
v tabeli (1).
Dokaz. Videli smo, da so v tabeli (1) natanko vsa naravna števila oblike
n = 2jk+ j + k (j, k ∈ N). Za takšno število n pa velja 2n+ 1 = 4jk+ 2i+
2k + 1 = (2j + 1)(2k + 1), kar pomeni, da 2n + 1 ni praštevilo. Po drugi
strani, če 2n+ 1 ni praštevilo, je produkt dveh lihih števil 2j + 1 in 2k + 1.
Iz 2n+ 1 = (2j+ 1)(2k+ 1) sledi, da je n = jk+ j+k, torej število iz tabele
(1).
S postopkom, ki mu rečemo Sundaramovo sito, lahko poǐsčemo vsa pra-
števila v neprazni končni množici števil M . Naj bo m najmanǰse naravno
število, za katerega velja n ≤ 2m+2 za vse n ∈M . Postopek poteka takole:
• naj bo M0 = M \ ({2k; k = 2, . . . ,m+ 1} ∪ {1}),
• za vsak j = 1, . . . , b2m−16 c, naj bo Mj = Mj−1 \ {(2j + 1)(2k + 1); k =
1, . . . , j}.
1–10 7
i
i
“Bracic” — 2019/6/26 — 8:14 — page 8 — #8 i
i
i
i
i
i
Janko Bračič
Na prvem koraku smo izločili soda sestavljena števila in število 1, na
drugem koraku pa liha sestavljena števila. V množici M
b2m−16 c
so ostala le
praštevila, ki so v M . Še pojasnilo, zakaj število j teče od 1 do b2m−16 c.
Namreč, vsako sestavljeno liho število v M je oblike (2j + 1)(2k + 1), kjer
je j ≥ k. Ker je vedno 2k + 1 ≥ 3, je dovolj, da je j ≤ b2m−16 c, saj za
b2m−16 c + 1 že velja 3
(
2(b2m−16 c + 1) + 1
)
≥ 3
(
22m−16 + 1
)
= 2m + 2. V
nekaterih primerih je res potrebno, da j teče do b2m−16 c. Naj bo na primer
p = 2t+1 > 3 liho praštevilo inM poljubna množica naravnih števil, v kateri
je 3p največje število. Ni težko videti, da je m = 3p−12 = 3t + 1 najmanǰse
naravno število, pri katerem velja n ≤ 2m + 2 za vse n ∈ M . Število 3p
je liho in sestavljeno, kot produkt dveh lihih naravnih števil različnih od 1
ga lahko zapǐsemo samo na en način: 3p = (2t + 1)(2 · 1 + 1). Se pravi,
da ga z zgornjim algoritmom izločimo iz množice M šele na koraku, ko je
j = t = b2m−16 c.
Evklidski generatorji praštevil
Na koncu se vrnimo k Evklidu in njegovemu dokazu, da je praštevil ne-
skončno mnogo. Generator praštevil, ki smo ga opisali v uvodu, je Mullin
[8] nekoliko spremenil in definiral dva generatorja praštevil. Prvo Mullinovo
zaporedje praštevil dobimo takole:
• naj bo q1 = 2,
• za vsak k ∈ N naj bo qk+1 najmanǰse praštevilo, ki deli q1 · · · qk + 1,
drugo Mullinovo zaporedje pa takole:
• naj bo Q1 = 2,
• za vsak k ∈ N naj bo Qk+1 največje praštevilo, ki deli Q1 · · ·Qk + 1.
V naslednji tabeli, ki je povzeta po [2], je prvih deset členov obeh zaporedij
8 Obzornik mat. fiz. 66 (2019) 1
i
i
“Bracic” — 2019/6/26 — 8:14 — page 9 — #9 i
i
i
i
i
i
Generatorji praštevil
k qk Qk
1 2 2
2 3 3
3 7 7
4 43 43
5 13 139
6 53 50 207
7 5 340 999
8 6 221 671 2 365 347 734 339
9 38 709 183 810 571 4 680 225 641 471 129
10 139 1 368 845 206 580 129
Zelo malo je znanega o teh dveh zaporedjih praštevil. Tako je še vedno
nerešen problem, ali se v zaporedju qk pojavijo vsa praštevila. Za zaporedje
Qk je Booker [2] pokazal, da v njem manjka neskončno mnogo praštevil.
Za konec poglejmo nekoliko drugačen evklidski generator praštevil, ki ga
je objavil Wooley leta 2017. Potrebujemo naslednjo lemo.
Lema 8 ([9]). Za vsako naravno število n je najmanǰse praštevilo, ki deli
nn
n − 1, enako najmanǰsemu praštevilu, ki ne deli n.
Dokaz. Za n = 1 trditev očitno velja, zato predpostavimo, da je n ≥ 2. Če
je n liho število, je 2 najmanǰse praštevilo, ki ne deli n. Očitno 2 deli nn
2−1.
Tudi obratno velja, če 2 deli nn
n − 1, potem je n liho število in je torej 2
najmanǰse praštevilo, ki ne deli n. Vzemimo zdaj, da je n sodo število. Naj
bodo q1, . . . , qk vsa praštevila, ki delijo n in p najmanǰse praštevilo, ki ne
deli n. Torej je p ≥ 3 in q1 · · · qk + 1 ≤ n + 1. Evklidov argument nam
zagotavlja, da obstaja praštevilo q, ki deli q1 · · · qk + 1. To praštevilo seveda
ne deli n in je manǰse kvečjemu enako q1 · · · qk+1. Ker pa je po predpostavki
p najmanǰse praštevilo, ki ne deli n, je p ≤ q in zato p ≤ q1 · · · qk +1 ≤ n+1.
Naj bodo p1, . . . , pj praštevila, ki delijo p−1, velja naj p−1 = pe11 · · · p
ej
j .
Potem zaradi pj < p in predpostavke, da je p najmanǰse praštevilo, ki ne deli
n, sledi, da je vsako od praštevil p1, . . . , pj v množici praštevil {q1, . . . , qk},
ki delijo n.
Za vsako praštevilo qi velja q
n
i ≥ 2n ≥ n + 1 ≥ p. Med drugim to velja
tudi za vsako praštevilo pi, ki deli p− 1. Torej je peii ≤ p− 1 < n+ 1 ≤ pni
oziroma ei < n za vse i = 1, . . . , j. Od tod sklepamo, da p − 1 deli število
(p1 · · · pj)n in torej tudi število nn. Naj bo d ∈ N takšno število, da je
1–10 9
i
i
“Bracic” — 2019/6/26 — 8:14 — page 10 — #10 i
i
i
i
i
i
Janko Bračič
nn = d(p − 1). Ker p ne deli n, lahko uporabimo mali Fermatov izrek in
dobimo nn
n
= (nd)p−1 ≡ 1 (mod p). Torej p deli nnn −1. Vsako praštevilo,
ki deli nn
n − 1, seveda ne deli n in je zato večje kvečjemu enako praštevilu
p, ki je najmanǰse praštevilo, ki ne deli n. Se pravi, da je p najmanǰse
praštevilo, ki deli nn
n − 1. Isti argument nam zagotavlja, da velja tudi
obratna implikacija. Če je p najmanǰse praštevilo, ki deli nn
n − 1, potem p
ne deli n. To praštevilo je najmanǰse med tistimi, ki ne delijo n, saj smo že
videli, da najmanǰse praštevilo, ki ne deli n, deli nn
n − 1.
Wooleyev generator praštevil je naslednji postopek:
• naj bo p1 = 2;
• za k ∈ N, k ≥ 2, naj bo n = p1 · · · pk−1 in pk najmanǰse praštevilo, ki
deli nn
n − 1.
Z uporabo leme 8 vidimo, da nam algoritem na k-tem koraku vrne k-
to najmanǰse praštevilo. Se pravi, s tem postopkom dobimo natanko vsa
praštevila, urejena po velikosti.
LITERATURA
[1] R. C. Baker, G. Harman in J. Pintz, The difference between consecutive primes, II,
Proceedings of the London Mathematical Society 83 (2001), 532–562.
[2] A. R. Booker, On Mullin’s second sequence of primes, Integers 12 (2012), 1167–1177.
[3] A. R. Booker in C. Pomerance, Squarefree smooth numbers and Euclidean prime
generators, Proceedings of the American Mathematical Society 145 (2017), 5035–
5042.
[4] Y. F. Cheng, Explicit estimate on primes between consecutive cubes, Rocky Mountain
Journal of Mathematics 40 (2010), 117–153.
[5] B. Green in T. Tao, The primes contain arbitrarily long arithmetic progressions,
Annals of Mathematics (2) 167 (2008), 481–547.
[6] N. Mackinnon, Prime number formulae, The Mathematical Gazette 71 (1987), 113–
114.
[7] W. H. Mills, A prime-representing function, Bulletin of the American Mathematical
Society 53 (1947), 604.
[8] A. A. Mullin, Recursive function theory. (A modern look at a Euclidean idea.), Bul-
letin of the American Mathematical Society 69 (1963), 737.
[9] T. D. Wooley, A Superpowered Euclidean prime generator, American Mathematical
Monthly 124 (2017), 351–352.
[10] Formula for primes, dostopno na en.wikipedia.org/wiki/Formula_for_primes,
ogled 22. 12. 2018.
[11] Sieve of Sundaram, dostopno na en.wikipedia.org/wiki/Sieve_of_Sundaram, ogled
22. 12. 2018.
10 Obzornik mat. fiz. 66 (2019) 1