PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 27 / 二次式素数

オイラーは以下の二次式を考案している。

n^2 + n + 41

この式は n を0から39までの連続する整数としたときに40個の素数を生成する。しかし, n = 40 のとき 4^02 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる。また,n = 41 のときは 41^2 + 41 + 41 であり明らかに41で割り切れる。

計算機を用いて n^2 - 79n + 1601 という式が発見できた。これは n = 0 から 79 の連続する整数で80個の素数を生成する。係数の積は -79x1601 で -126479である。

さて, |a| < 1000, |b|≤1000 として以下の二次式を考える。

n^2 + an + b

n = 0 からはじめて連続する整数で素数を生成したときに最長の長さとなる上の二次式の係数 a, b の積を答えよ。


Problem 27 - Project Euler

まず (a, b) に対して {素数列の長さ, 積 abの値} を返す関数を作ります。(a, b)=(1, 41) でチェックしました。


計算の前に a, b の候補をしぼりこんでおきます。以下,g(n)=n^2+an+b です。

■bは素数

g(0)=b は素数です。

■b≠±2

b が偶数なら g(2m)=4m^2+2ma+b はすべて偶数。偶数の素数は2だけなので,これは不合理。b は奇素数です。

■aは奇数

a が偶数なら g(2m-1)=(2m-1)^2+a(2m-1)+b はすべて偶数。これはありえないので a は奇数です。

以上をもとに書いたコードがこちらです。


variee.hatenadiary.com