« 君はRiemann予想を解いているに違いない | トップページ | 早朝に見た虹 »

2012/09/17

素数を100万個計算してみた

Riemann 予想について昨日ポストするきっかけとなった NHK-BS の番組の中には,非常に興味深い説明がいくつか出てきます.その一つは素数の分布.素数を小さなほうから順に並べてみると,

2, 3, 5, 7,
11, 13, 17, 19,
23, 29,
31, 37,
41, 43, 47,
53, 59,
61, 67,
71, 73, 79,
83, 89,
97,
101, 103, 107, 109,
・・・

という数列になります.ここで面白いのは素数が現れる間隔です.2以外の偶数は素数ではないので当然ですが,隣り合う奇数が互いに素数の場合もあれば,そうでない場合もある.10台には4つも素数があるのに,90台には素数は一つしかない.10台はまだ小さな数なので素数が多くあってもおかしくないと思うものの,100台にも4つの素数があったりします.

これは面白いと思って,早速 Ruby で素数を見つけるスクリプトを書き,それを走らせて100万個の素数を計算してみました.素数判定のアルゴリズムは最も素朴に,既知の素数で割り算していって割り切れなかったらそいつは素数,といういわゆる試し割りです.これだと膨大な数の素数を計算するには計算効率が悪すぎて実用的ではないのですが,最初の100万個を計算するくらいであれば,この素朴さで,かつインタプリタ言語の Ruby でも十分だろうと踏んでやってみました.

Core i7 Nehalem (2.8GHz) という二世代前の CPU を搭載した Windows 7 上で100万個を計算するのにかかった時間は69.85秒.十分に速くて申し分ありません.この結果を基に,この範囲で素数の間隔を計測してみました.最も長い間隔は何と 154 です.具体的に特定すると,

325852 番目の素数 4652353 と,
325853 番目の素数 4652507 との間,

733588 番目の素数 11113933 と,
733589 番目の素数 11114087 との間,

983015 番目の素数 15203977 と,
983016 番目の素数 15204131 との間,

がそれぞれ 154 離れていることがわかりました.つまり,この間は 154 ものあいだ素数が無い砂漠のような領域だということがわかります.次に長い間隔はもちろん 152 なのですが,この間隔を持つ領域は100万個の中には1か所しかありません.その次の 150 の間隔を持つ領域も1か所だけ.さらに 148 の間隔を持つ領域は2か所あります.

Wikipedia の素数の解説からいろいろと引用していますが,"任意に大きな n に対して,n! + 2 から n! + n までは全て合成数である" と言えます.先ほどの三つの例でいうと,それらの素数に近い階乗は,10! = 3628800,11! = 39916800 なので,この理屈で合成数の砂漠が広がっているわけではありません.

なかなか面白いですね.しかし,これら素数を二次元平面上にプロットしてみると,局所的には間隔の不揃いのデコボコはあるものの,大域的には非常に滑らかに(補正)対数積分のグラフに漸近していることがわかります.これが素数定理.まだ少年だったガウスがすでに見出していたとのこと.驚きますね.

ところで,今日わかっている最大の素数は,2^43112609 - 1 という数だそうです.大きすぎて目が眩みますね.

|

« 君はRiemann予想を解いているに違いない | トップページ | 早朝に見た虹 »

IT関連情報」カテゴリの記事

科学」カテゴリの記事

コメント

こんな記事をポストした矢先に,まだまだ若い京大教授が,世紀の難問 ABC 予想を証明する論文を発表した,というニュースが飛び込んできました.私には何のことやら全く理解できませんが,証明できたとすると,フェルマーの定理などもこの ABC 予想の系として証明できるそうで,ひょっとすると大発見.しかも,証明のために開発された新しい手法があり,この手法そのものの価値も非常に高いとのことです.

今後,年単位での検証が行われると思いますが,大いに期待できそうです.

投稿: 俊(とし) | 2012/09/19 21:39

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/54612/55678431

この記事へのトラックバック一覧です: 素数を100万個計算してみた:

» 今度は素数を1000万個計算してみた [望湖庵日記 Lakeside Diary]
先週と同じように 素数を計算していって,今週は1000万個まで計算することができました.ただし素朴な試し割りで計算しているので,案の定計算時間が加速度的に伸び,100万個までが約70秒で済んだのに対して,2159秒もかかってしまいました.もうこのあたりが限界ではないかと思いますが,その気になればさらに10倍の1億個程度... [続きを読む]

受信: 2012/09/23 15:44

« 君はRiemann予想を解いているに違いない | トップページ | 早朝に見た虹 »