読者です 読者をやめる 読者になる 読者になる

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) に対して素数列の長さを返す関数を作ります。(a, b)=(1, 41) でチェックしました。


これを For ループにかける前に 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 は奇数です。

以上をもとに書いたコードがこちらです。面倒なので b≠±2 は反映しませんでした。計算時間は2.2秒。ためしに a, b の範囲をしぼりこまないで計算させてみたら22秒でした。


For ループを使わない解法も考えてみました。やり方は問題119と同じで,Tuples で {a, b} を作って,判定条件に渡してます。こちらの方がよい解法だと思いますが,問題119同様,時間はあまり変わらないですね。


variee.hatenadiary.com