素数を列挙する

数学者が数学を「語る」ことの良さ - hiroyukikojimaの日記で紹介されていた、

リーマン予想は解決するのか? ―絶対数学の戦略―

を一昨日買って、昨日最初の対談をざーっと読んだ。残念ながらあまり理解はしていない。
その最初のほうに書かれていたのが、古代ギリシャの素数が無限にあることの証明を背理法で求めるというもの。実はあれはウソなんだとか。ウソというのは、もちろんその証明は間違っていなくて、ギリシャでは背理法じゃなくて構成的な方法で素数を次々と作っていけるというものだったということだったらしい。p₁,...,p_nという素数があったとして、p₁...p_n + 1を考える。これが素数なのか素数でないのかはわからないが、素数ならもちろん新たに素数が作られたわけだ。素数でなければなんらかの素数に分けることができるが、p₁,...,p_nでは割り切れないのだから、やはり新たに素数が、今度は複数作られたことになる。
背理法のほうはたぶん高校で習ったと思うが、これを聞いたとき「なるほどー」くらいの感想しかなかったと思う。自分でも証明を思いつきそうな気がしたから。しかし、この構成的な方法は衝撃的だ。

じゃあ、実際にこの方法でどのように素数が生成されるのかPythonで書いてみた。なんの工夫もない。

def add(s, a):

    for e in a:

        if s.count(e) == 0:

            s.append(e)
def factorize(n, p = 2):

    s = [ ]

    while p * p <= n:

        if n % p == 0:

            n /= p

            s = [ p ]

            add(s, factorize(n, p))

            return s

        if p == 2:

            p = 3

        else:

            p += 2

    if n > 1:

        s += [ n ]

    return s
N = 7

p = [ 2 ]

for n in xrange(N):

    add(p, factorize(reduce(lambda x, y: x * y, p, 1) + 1))

print p

2から始めて結果はこう。

[2, 3, 7, 43, 13, 139, 3263443, 547, 607, 1033, 31051L, 29881, 67003,

9119521, 6212157481L]

上に書かれた作業は7回しか繰り返せなくて、8回目をやろうとしてももう返ってこない。化け物のようだ。いったい、いつ5が出てくるのだろうか。