素数は、初めの方は、
2, 3, 5, 7, 11, 13, ...
となっていて、ほとんど、2か4程度しか離れていないが、もう少し先に進むと、
113, 127, ...
のように、大きく間隔が開くケースが出てくる。この場合は 127−113=14 離れている。
合成数のペアであれば、例えば、n!+2 からはじまる (n−1) 個の数
n!+2, n!+3, ... , n!+n
は、全て合成数なので、(n!+1 , n!+n+1) のように、間隔がn離れているペアを容易に構成できる。
しかし、素数の場合は簡単に構成することはできず、基本的にしらみつぶし探査しかない。
10 P=2:M=0
20 N=nxtprm(P):G=N-P
30 if G<=M then 50
40 print G;":";P;",";N:M=G
50 P=N:goto 30
nxtprm(P) は P の次の値を返す関数であり、返す値の最大値は 4294967291 (=232−5) である。
よって、このプログラムで (2, 3) から (4294967279, 4294967291) までの探査が可能である。
この問題はあまりにも単純過ぎて、これまであまりやる気がしなかった。
ループが単純なnのオーダなので、工夫の入り込む余地がなく、
純粋にマシンパワーの勝負となってしまうからである。
しかし、問題を、
と拡張すると、多少おもしろくなる。
上のプログラムでは M にギャップの最大値を格納して、ギャップ G が Mを越えた場合に
値を表示するようになっているが、その部分を M という1個の変数ではなく、
配列として持ち、その値が始めて出たとき、ギャップと、その素数を表示するように変更する。
ついでに、その素数が何番目の素数かもカウントする。プログラムは以下のとおり。
10 dim A%(1000):for I%=1 to 1000:A%(I%)=0:next I%
20 P=2:C=1
30 N=nxtprm(P):G=N-P
40 if A%(G)=1 then 60
50 print G;":";P;",";N;":";C:A%(G)=1
60 P=N:inc C:goto 30
メインループで時間のかかる処理は nxtprm() で、これが全体の時間を支配する。
それ以外の処理は、引き算 G=N-P, 比較、代入、インクリメントの4つで、
もし、カウントをやらなければ処理時間を 1/4 削れることとなるが、
あとから、何番目の素数かを調べるには、結局カウントするしかないので、
とりあえずこのままにしておく。
実行結果をギャップの大きさ順にソートした結果は以下のとおり。
-----+---------------------------+------------
g | pn , pn+1 | n
-----+---------------------------+------------
1 | 2 , 3 | 1
2 | 3 , 5 | 2
4 | 7 , 11 | 4
6 | 23 , 29 | 9
8 | 89 , 97 | 24
10 | 139 , 149 | 34
12 | 199 , 211 | 46
14 | 113 , 127 | 30
16 | 1831 , 1847 | 282
18 | 523 , 541 | 99
20 | 887 , 907 | 154
22 | 1129 , 1151 | 189
24 | 1669 , 1693 | 263
26 | 2477 , 2503 | 367
28 | 2971 , 2999 | 429
30 | 4297 , 4327 | 590
32 | 5591 , 5623 | 738
34 | 1327 , 1361 | 217
36 | 9551 , 9587 | 1183
38 | 30593 , 30631 | 3302
40 | 19333 , 19373 | 2191
42 | 16141 , 16183 | 1879
44 | 15683 , 15727 | 1831
46 | 81463 , 81509 | 7970
48 | 28229 , 28277 | 3077
50 | 31907 , 31957 | 3427
52 | 19609 , 19661 | 2225
54 | 35617 , 35671 | 3793
56 | 82073 , 82129 | 8028
58 | 44293 , 44351 | 4612
60 | 43331 , 43391 | 4522
62 | 34061 , 34123 | 3644
64 | 89689 , 89753 | 8688
66 | 162143 , 162209 | 14862
68 | 134513 , 134581 | 12542
70 | 173359 , 173429 | 15783
72 | 31397 , 31469 | 3385
74 | 404597 , 404671 | 34202
76 | 212701 , 212777 | 19026
78 | 188029 , 188107 | 17006
80 | 542603 , 542683 | 44773
82 | 265621 , 265703 | 23283
84 | 461717 , 461801 | 38590
86 | 155921 , 156007 | 14357
88 | 544279 , 544367 | 44903
90 | 404851 , 404941 | 34215
92 | 927869 , 927961 | 73321
94 | 1100977 , 1101071 | 85787
96 | 360653 , 360749 | 30802
98 | 604073 , 604171 | 49414
100 | 396733 , 396833 | 33608
102 | 1444309 , 1444411 | 110224
104 | 1388483 , 1388587 | 106286
106 | 1098847 , 1098953 | 85633
108 | 2238823 , 2238931 | 165326
110 | 1468277 , 1468387 | 111924
112 | 370261 , 370373 | 31545
114 | 492113 , 492227 | 40933
116 | 5845193 , 5845309 | 402884
118 | 1349533 , 1349651 | 103520
120 | 1895359 , 1895479 | 141718
122 | 3117299 , 3117421 | 224659
124 | 6752623 , 6752747 | 460883
126 | 1671781 , 1671907 | 126172
128 | 3851459 , 3851587 | 273413
130 | 5518687 , 5518817 | 381995
132 | 1357201 , 1357333 | 104071
134 | 6958667 , 6958801 | 474029
136 | 6371401 , 6371537 | 436612
138 | 3826019 , 3826157 | 271743
140 | 7621259 , 7621399 | 515910
142 | 10343761 , 10343903 | 685903
144 | 11981443 , 11981587 | 786922
146 | 6034247 , 6034393 | 415069
148 | 2010733 , 2010881 | 149689
150 | 13626257 , 13626407 | 887313
152 | 8421251 , 8421403 | 566214
154 | 4652353 , 4652507 | 325852
156 | 17983717 , 17983873 | 1150400
158 | 49269581 , 49269739 | 2959782
160 | 33803689 , 33803849 | 2078068
162 | 39175217 , 39175379 | 2386432
164 | 20285099 , 20285263 | 1287544
166 | 83751121 , 83751287 | 4875380
168 | 37305713 , 37305881 | 2279181
170 | 27915737 , 27915907 | 1736516
172 | 38394127 , 38394299 | 2341680
174 | 52721113 , 52721287 | 3154380
176 | 38089277 , 38089453 | 2324140
178 | 39389989 , 39390167 | 2398788
180 | 17051707 , 17051887 | 1094421
182 | 36271601 , 36271783 | 2219883
184 | 79167733 , 79167917 | 4623702
186 | 147684137 , 147684323 | 8321465
188 | 134065829 , 134066017 | 7595444
190 | 142414669 , 142414859 | 8040878
192 | 123454691 , 123454883 | 7027147
194 | 166726367 , 166726561 | 9330121
196 | 70396393 , 70396589 | 4140009
198 | 46006769 , 46006967 | 2775456
200 | 378043979 , 378044179 | 20226285
202 | 107534587 , 107534789 | 6169832
204 | 112098817 , 112099021 | 6416467
206 | 232423823 , 232424029 | 12768473
208 | 192983851 , 192984059 | 10711737
210 | 20831323 , 20831533 | 1319945
212 | 215949407 , 215949619 | 11911710
214 | 253878403 , 253878617 | 13879771
216 | 202551667 , 202551883 | 11212381
218 | 327966101 , 327966319 | 17681799
220 | 47326693 , 47326913 | 2850174
222 | 122164747 , 122164969 | 6957876
224 | 409866323 , 409866547 | 21833975
226 | 519653371 , 519653597 | 27335370
228 | 895858039 , 895858267 | 45808557
230 | 607010093 , 607010323 | 31671709
232 | 525436489 , 525436721 | 27623436
234 | 189695659 , 189695893 | 10539432
236 | 216668603 , 216668839 | 11949206
238 | 673919143 , 673919381 | 34971241
240 | 391995431 , 391995671 | 20931911
242 | 367876529 , 367876771 | 19710938
244 | 693103639 , 693103883 | 35914201
246 | 555142061 , 555142307 | 29101114
248 | 191912783 , 191913031 | 10655462
250 | 387096133 , 387096383 | 20684332
252 | 630045137 , 630045389 | 32809470
254 | 1202442089 , 1202442343 | 60571237
256 | 1872851947 , 1872852203 | 92276646
258 | 1316355323 , 1316355581 | 66007695
260 | 944192807 , 944193067 | 48150537
262 | 1649328997 , 1649329259 | 81777689
264 | 2357881993 , 2357882257 | 114867712
266 | 1438779821 , 1438780087 | 71825213
268 | 1579306789 , 1579307057 | 78475129
270 | 1391048047 , 1391048317 | 69560248
272 | 1851255191 , 1851255463 | 91265087
274 | 1282463269 , 1282463543 | 64392899
276 | 649580171 , 649580447 | 33772762
278 | 4260928601 , 4260928879 | 201745031
280 | 1855047163 , 1855047443 | 91442723
282 | 436273009 , 436273291 | 23163298
284 | 1667186459 , 1667186743 | 82618492
286 | 2842739311 , 2842739597 | 137234530
288 | 1294268491 , 1294268779 | 64955634
290 | 1948819133 , 1948819423 | 95831003
292 | 1453168141 , 1453168433 | 72507380
304 | 2433630109 , 2433630413 | 118374763
306 | 3917587237 , 3917587543 | 186232616
310 | 4024713661 , 4024713971 | 191079089
320 | 2300942549 , 2300942869 | 112228683
336 | 3842610773 , 3842611109 | 182837804
-----+---------------------------+------------
計算時間は、Pentium MMX (233MHz) で、約4日かかった。
この問題については、Dr. Thomas R. Nicely, Dr. Bertil Nyman が精力的に探査を続けており、
こちらのページ(First occurrence prime gaps)
で最新の状況が公開されている。
現在の状況は以下のとおり。
これはおそらく、必ず存在するであろう。
簡単に証明できそうな気もするが、双子素数なみの難問かも知れない。
素数のギャップが取りうる値の頻度。
はじめは2、4が多いが、そのうち、6の方が多くなる。
特に、30が最も多くなるのはいつか。
へのチャレンジが可能となる。
30とまではいかなくても、各偶数の頻度の推移をトレースすること。
特に、6がチャンピオンの座を降りるのはいつか。
例えば、プログラムは以下のとおり。
10 ' gap_n.ub
20 word 10
30 dim T(1000):for I%=0 to 1000:T(I%)=0:next I%
40 P=2:I=1:M=0:B=0
50 N=nxtprm(P):G=N-P:inc T(G)
60 if T(G)>M then M=T(G) else goto 80
70 if G<>B then print G;":";T(G);":";P;",";N;":";I:B=G
80 P=N:inc I:goto 50
少し走らせると、以下のような結果が得られる。
---+----+-----------+-----
g |cnt.| pn , pn+1 | n
---+----+-----------+-----
1 | 1 | 2 , 3 | 1
2 | 2 | 5 , 7 | 3
4 | 11 | 127 , 131 | 31
2 | 12 | 149 , 151 | 35
6 | 22 | 383 , 389 | 76
2 | 23 | 431 , 433 | 83
6 | 24 | 443 , 449 | 86
4 | 25 | 487 , 491 | 93
6 | 27 | 557 , 563 | 102
---+----+-----------+-----
これ以降、新たな値は、出力される気配がない。
『数論……』によると、少なくとも 1014 以下では6がトップであり、
それ以降、いつ、6以外の数がトップになるかは、知られていない。
このプログラムを実行すると、双子素数の異常な多さがよくわかる。
(間隔6、間隔12に継ぐ頻度で現われる)
また「間隔6が多い」ということから、素数生成のための効率的な手段が得られる。
通常であれば、
とするが、素数の間隔が2よりも6となる場合の方が圧倒的に多いため、
初めの数は 6n+1 または 6n+5 とし、n=n+2 のかわりに n=n+6 とすればよい。
『枕草子*砂の本』 |
---|