連続する2素数間のギャップ


(注:フォントをMSゴシックにすると見やすくなります)

  1. 『数論における未解決問題集』A8で、連続する2素数の間の間隔がどのぐらい大きくなるか、 を問題としている。

    素数は、初めの方は、

    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離れているペアを容易に構成できる。
    しかし、素数の場合は簡単に構成することはできず、基本的にしらみつぶし探査しかない。


  2. 以下のようなプログラムで、差が大きくなるような素数の組を しらみつぶしに探査することができる。

    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のオーダなので、工夫の入り込む余地がなく、
    純粋にマシンパワーの勝負となってしまうからである。
    しかし、問題を、

    と拡張すると、多少おもしろくなる。


  3. 上のプログラムを修正する。

    上のプログラムでは 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) で最新の状況が公開されている。

    現在の状況は以下のとおり。


  4. Open Problem

    1. 2以外の素数は全て奇数なので、素数間のギャップは、1以外は全て偶数となる。
      逆に、任意の偶数について、それをギャップとするような素数の組は存在するか。

      これはおそらく、必ず存在するであろう。
      簡単に証明できそうな気もするが、双子素数なみの難問かも知れない。

    2. 特に、素数の間隔が 1000 となるのはいつか。
      或いは、1000 以下の全ての偶数について、その値をとる素数の組を求めること。
      現在、968, 976, 980, 982, 986, 1000 が未解決である。
      また、996は解(1000040940998065943, 1000040940998066939)が見つかっているが、最小性が確認されていない。

    3. 上のプログラムを少し修正することにより、『数論……』A8のもう一つの問題、

      素数のギャップが取りうる値の頻度。
      はじめは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が多い」ということから、素数生成のための効率的な手段が得られる。
      通常であれば、

      1. 適当な奇数 n を選ぶ
      2. 小さな数との gcd をとる
      3. gcd が1より大きければ n=n+2 として goto 2
      4. 素数判定を行う
      5. 素数ならば終了。そうでなければ n=n+2 として goto 2

      とするが、素数の間隔が2よりも6となる場合の方が圧倒的に多いため、
      初めの数は 6n+1 または 6n+5 とし、n=n+2 のかわりに n=n+6 とすればよい。


  『枕草子*砂の本』  

E-mail : kc2h-msm@asahi-net.or.jp 三島 久典