reseto za iskanje prastevilskih dvojčkov
SRECKO LAMPRET
Osnovna sola Vuzenica
Math. Subj. Class. (2010): 11A41
V članku izpeljemo novo karakterizacijo praStevilskih dvojčkov. S tem rezultatom dobimo elementarno metodo za iskanje praStevilskih dvojčkov do poljubno izbranega naravnega Stevila.
SIEVING TWIN PRIME PAIRS
In this paper a new characterization of twin prime pairs is obtained. This result gives us an elementary method for finding twin prime pairs up to a given integer.
Prastevilski dvojček je par praStevil oblike (p, p + 2). Razen 2 in 3 ima vsako praStevilo obliko 6k — 1 ali 6k + 1. Zato je vsak prastevilski dvoj-Cek, razen (3, 5), oblike (6k — 1,6k + 1) za neko naravno število k. V tem Clanku predstavljamo elementarno metodo za iskanje prastevilskih dvojCkov do poljubnega naravnega stevila, ki temelji na spodnjih rezultatih.
Lema 1. Naj bo p pračtevilo oblike p = 6j + 1 ali p = 6j — 1. Potem za vsako naravno čtevilo i
(6(pi + j) — 1, 6(pi + j) + 1) in (6(pi — j) — 1, 6(pi — j) + 1)
nista praStevilska dvojčka.
Dokaz. Najprej predpostavimo, da je p = 6j + 1. Potem sta 6 (pi + j) +1 = 6pi + p = p (6i + 1) in 6 (pi — j) — 1 = 6pi — p = p (6i — 1) sestavljeni stevili za vsako naravno stevilo i. Podobno, Ce je p = 6j — 1, vidimo, da sta 6 (pi + j) — 1 in 6 (pi — j) + 1 sestavljeni stevili za vsako naravno stevilo i.m
Izrek 2. Naj bo k naravno stevilo. Potem (6k — 1,6k + 1) ni prastevilski dvojček natanko tedaj, ko obstaja prastevilo p ^ V6k + 1 oblike 6j ± 1 in tako naravno stevilo i, da je k = pi + j ali k = pi — j.
Dokaz. Najprej predpostavimo, da (6k — 1, 6k + 1) ni prastevilski dvojCek. Potem bodisi 6k — 1 ali 6k + 1 ni prastevilo.
Oglejmo si primer, ko 6k — 1 ni prastevilo. Potem obstaja tako prastevilo p < V6k — 1 < V6k + 1, da p deli 6k — 1. Zato p = 2,3. Po izreku o deljenju z ostankom obstajata taki nenegativni Celi stevili n, r, da je k = pn + r in
0 ^ r < p. Posledično velja p | 6 (pn + r) - 1 = 6pn + (6r - 1) in zato p | 6r - 1. Ker je 6r - 1 = pt za neko naravno Stevilo t in r < p, vidimo, da je
6r - 1 6p - 1 ^
t =-^ —-< 6.
pp
Zato je t G {1,2,3,4, 5} in 6r - tp = 1. To pomeni, da sta 6 in t tuji si Stevili in potemtakem t = 1 ali t = 5. Ker p = 2,3, velja bodisi p = 6j - 1 ali p = 6j + 1 za neko naravno stevilo j.
Sprva si oglejmo primer, ko je p = 6j -1. Ce je t = 5, sledi 1 = 6r - 5p = p (mod 6), kar je nemogoče. Torej t = 1 in zato je p = 6r - 1. Potem velja r = j in zato je k = pi + j za i := n. Pri tem velja, da je i > 0, kajti če bi bil i = 0, bi veljalo k = r in zato 6k - 1 = 6r - 1 = p, kar nas privede do protislovja.
Sedaj si oglejmo primer, ko je p = 6j + 1. Ce je t = 1, sledi p = 6r - 1 = -1 (mod 6), kar je nemogoče. Torej t = 5 in zato 6r - 1 = 5p = 30j + 5. Tako je r = 5j + 1 = p - j in zato k = pn + p - j = pi - j za i := n + 1 > 0. V primeru, ko 6k + 1 ni prastevilo, dokaz poteka podobno. Obratna implikacija sledi iz leme 1.	■
Sledi opis delovanja algoritma oz. reseta za iskanje prastevilskih dvojčkov do poljubnega naravnega stevila n.
1.	Napravimo seznam naravnih stevil k = 1, 2,...,
2.	Poisčemo vsa prastevila 3 < p ^ ^n.
Pomagamo si lahko z Eratostenovim resetom. Tako kot pri Eratoste-novem resetu tudi tu zadosča izvajati algoritem le tako dolgo, dokler prastevila ne dosezejo vrednosti ^/n, saj v vsaki faktorizačiji vsaj en faktor ne presega tega stevila.
3.	Za vsako prastevilo 3 < p ^ naredimo sledeče:
-	če 6 | p + 1, potem j = ^+r1, sičer j = 1;
-	prečrtamo vsa stevila k = pi + j in k = pi - j za vsak i = 1,2,... z nasega seznama.
4.	Vsako preostalo naravno stevilo k s seznama nam da prastevilski dvojček (6k - 1, 6k + 1).
Skličujoč se na izrek 2, s to metodo dobimo vse prastevilske dvojčke do n, razen para (3, 5). V naslednjem primeru predstavimo konkretno delovanje tega algoritma za n = 250.
Primer 1. Poiščimo vse prastevilske dvojčke do 250. Napravimo seznam naravnih stevil k = 1,2,..., 42. Nato poiscemo vsa prastevila 3 < p < \/250. V nasem primeru so to 5, 7,11,13.
(i)	Za p = 5 = 6 ■ 1 — 1 velja j = 1 in zato iz nasega seznama prečrtamo vsa naravna stevila k oblik 5i — 1 in 5i + 1.
(ii)	Za p = 7 = 6 ■ 1 + 1 velja j = 1 in zato iz nasega seznama prečrtamo vsa naravna stevila k oblik 7i — 1 in 7i + 1.
(iii)	Za p = 11 = 6 ■ 2 — 1 velja j = 2 in zato iz nasega seznama prečrtamo vsa naravna stevila k oblik 11i — 2 in 11i + 2.
(iv)	Za p = 13 = 6 ■ 2 + 1 velja j = 2 in zato iz nasega seznama prečrtamo vsa naravna stevila k oblik 13i — 2 in 13i + 2.
123456789 10 11 12 13 14 15 16 17 18 19 ^ 21 22 23 24 25 ^ 28 29 30 31 32 33 34 35 ^ ^ 38 39 40 41 42
Za vsako preostalo naravno stevilo k iz nasega seznama dobimo prastevilski dvojček (6k — 1,6k + 1). Ce dodamo se par (3, 5), dobimo vse prastevilske dvojčke do 250:
(3, 5), (5, 7), (11,13), (17,19), (29, 31), (41, 43), (59, 61), (71, 73), (101,103),(107,109),(137,139), (149,151), (179,181), (191,193), (197,199), (227, 229), (239, 241).
Obstajajo tudi nekateri drugi algoritmi za iskanje prastevilskih dvojčkov, ki pa večinoma niso elementarni. Pri drugih, ki so elementarni, pa je, če hočemo poiskati prastevilske dvojčke do nekega poljubnega naravnega stevila n, ponavadi treba najprej poiskati vsa prastevila do n in nato med njimi po raznih metodah črtamo vsa tista prastevila, ki niso del dvojčka. Pri algoritmu, ki je tu predstavljen, pa lahko poisčemo vse prastevilske dvojčke do n, pri tem pa je predhodno (npr. z Eratostenovim resetom) treba poiskati le prastevila d^ ^/n, kar je za dovolj velike n lahko prečejsnja prednost.
Zahvala. Avtor se zahvaljuje dr. Danielu Eremiti za strokovne nasvete in tehnično pomoč pri nastajanju članka. Zahvaljuje se tudi rečenzentu za koristne predloge in skrbno branje članka.