1
素数が無限に存在することは古代ギリシャで既に知られていた。
紀元前に編纂された『原論』には以下のような感じの証明が書かれているとか。
素数が 3 個しか無いとしよう。これを $p$, $q$, $r$ とする。
$pqr+1$ は $p$, $q$, $r$ のどれで割っても $1$ が余る。
これは素数が $p$, $q$, $r$ だけという仮定に反する。
(この論法は素数が 4 個でも 5 個でも同様。つまり,素数が有限個と仮定すれば必ず矛盾が導かれる)
背理法(仮定 A から矛盾を導いて A の否定を証明する論法)を使っている。
中学でこの証明に出会ったときちょっとした感動を覚えた。
背理法がカッコよかったし,「全素数の総積プラス 1」という単純な式から実に簡単に矛盾を引き出したところが見事だと思った。
2
同じ頃「大きな素数探し」というテーマがあることを知った。
電子計算機の進歩とともに,手計算では到底見出せないような巨大な素数が次々見つかり,何年にどこの誰がどんな素数を見つけた,というような一覧表が作られているのも何かで見た。
3
私のような素人は,『原論』の件の証明を思い出して,ついこんな間違ったことを考えついてしまう。
見つかった素数を全部掛け合わせて 1 を足せば簡単に巨大素数が得られるじゃん!
もちろんそんなはずはない。
有限個との仮定から,その総積プラス 1 がどれでも割り切れない,という事態が導かれただけのことだ。実際には素数は無限にあり,そこから有限個の素数をとり出して掛け合わせて 1 を足したからといって,それが素数になるとは限らない。
4
しかしだよ?
$n$ 個の素数の総積に 1 を足した数は,少なくともそれらの素数では割り切れない。だから,ある意味「割り切りにくい数」であるとはいえるのではないか。
もっと言えば,そいつらの中にけっこう素数があるんじゃないか?
エラトステネスの篩を考えると,合成数を排除するには小さい素数の倍数を排除すると効率が良さそうな気がする。
それゆえ,素数を小さい順に並べて,最初の $n$ 個を取り,それらの総積に 1 を足して試すのがよさそう。
5
まず,最初の素数 $2$ を取り上げる。
これに $1$ を足した $3$ は素数だ。
次。
$2\cdot3+1=7$ は素数。いいね。
$2\cdot3\cdot5+1=31$ も素数。うーん,いい調子。
$2\cdot3\cdot5\cdot7+1=211$ はどうだ?
$11$ でも $13$ でも割り切れないのはすぐに分かる。$17^2$ は $211$ を越えてしまうから試す必要もない。
素数と分かった。んー,なんか話がうま過ぎない?
ここまで,手計算でがんばった。
$2\cdot3\cdot5\cdot7\cdot11+1=2311$ はどうだ?
手計算は諦めた。そう難しくはないが,計算間違いをしないという自信が無い。
ここでターミナルに
irb -r prime
と打つ。
これで,Ruby の対話環境が起動し,素数ライブラリーである prime
が読み込まれた状態になる。
そして,
irb(main):001:0> 2311.prime?
=> true
おおー,これも素数か!
(ある整数が素数であることは Integer#prime? で確認できる)
まさかこんなにうまく素数ばかり出てくるとは思わなかった。
6
ではプログラムで組織的に調べてみよう。
Ruby で以下のように書く。
require "prime"
1.step do |n|
m = Prime.take(n).inject(:*) + 1
puts "%3d %s %d" % [n, (m.prime? ? "o" : "x"), m]
end
このプログラムは止まるように書いていない。形式上は無限に調べ続けるようになっている。
Prime.take(n)
で最初の n
個の素数の配列が得られる。
inject(:*)
でその総積が得られる。
そして,
-
n
の値 - 素数かどうか(素数なら
o
,そうでないならx
) - 「総積プラス 1」の値
とを並べて表示するだけ。
7
結果は以下のようであった。
1 o 3
2 o 7
3 o 31
4 o 211
5 o 2311
6 x 30031
7 x 510511
8 x 9699691
9 x 223092871
10 x 6469693231
11 o 200560490131
12 x 7420738134811
13 x 304250263527211
14 x 13082761331670031
15 x 614889782588491411
16 x 32589158477190044731
17 x 1922760350154212639071
18 x 117288381359406970983271
$n = 18$ までは一気に進むが,そこから先はいつまで経っても進まない。
$n = 5$ までは素数だったのに,そのあとは合成数が続く。うーむ残念。
$n = 11$ でようやくまた素数が現れたと思ったら,またまた合成数が続いていく。
「けっこうな割合で素数が含まれているのでは」と思ったのはやはり幻想だったか。