素数について愛を語らう。

気持ち悪いタイトルですみません。


先日会社の同僚に
「素数好きの割にはブログで素数について書いてないんだww」
と言われてしまったので、
久々に素数に対する情熱を思い出す機会を無理やり設けてみました。


「素数って何?」と言う人がもしいたら、それは
「料理をしたことがないまま成人を迎えた良家のお嬢様」か、
あるいは
「人間とはなんだろうかと常に自問し続ける哲学者の小粋なジョーク」
だと思うのですが、
少しでも素数に興味を持ってくれる人が増えることを願ってやまないので、
念のため説明しておきます。


素数というのは「約数がちょうど2個ある自然数」です。
つまり、

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

と無限に存在します。
「約数が3つ以上ある自然数」のことは合成数といいます。
「約数が1つしかない自然数」は1だけで、
1は素数でも合成数でもありません。


素数の分布にどんな意味があるのか、どのような分布になっているのか、
未だに解明されていません。
「11と13」とか「59と61」のように差が2の素数の組が双子の素数と呼ばれたり、
連続してなかなか素数が見つからない範囲のことが素数砂漠と呼ばれたり、
素数に関する言葉を聞くだけでも胸が躍る感じがあるのですが、
それらがどのような性質を持っているのかということについても謎が多いのです。


どうでしょう、興味が沸いてきたことと思います。
あなたはきっと寝る前に「あれ? 101って素数なのかな? じゃあ1001は?」と考えてしまうことでしょう。
これであなたも私と同類です。
ようこそ、こちら側の世界へ。
(1001とか11の倍数じゃねーか、と一蹴できる人は私と親友になれそうな気がします。)


さらに追い打ちをかけてみることにします。
先程サラリと素数が無限に存在すると書きましたが、
ユークリッドによってなされた以下のような証明が最も有名です。

有限個(n個)の素数があり、それを p1, p2, p3, ... pn とする。
N = p1 × p2 × p3 × ... × pn + 1
とする。
Nは素数か合成数のいずれかであるが、
Nが素数の場合、n+1個目の素数としてNを見つけたことになる。
Nが合成数の場合、Nは p1, p2, p3, ... pn のいずれによっても割り切ることができないので、
Nを割る別の素数 p が存在するはずである。

つまり、n個の素数が存在すれば、確実にn+1個の素数が存在する。
よって素数は無限に存在する。

証明終了。

か、かっこいい…。


原文は確か背理法で証明されていたと思うのですが、
上記のような帰納法での証明を小学生の頃に見せられて、
それから素数の虜になってしまったわけです。
「オレが素数分布を求めてやるッ!」
と。


それからというもの、新たにプログラミング言語を学ぶ際は
必ず素数判定のプログラムを作ってきましたし、
慶応大学環境情報学部の入試問題で素数絡みの問題を解いたときは歓喜しましたし、
大学の頃にやったコントで「素数かよ!」というツッコミもしたわけです。


結局、大学に入る前に数学科への道は挫折したのですが、
そろそろブログが長くなってきましたので続きはまた今度にします。
なんとなく、第3部まで続きそうな予感がします。



プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)

プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)