PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 58 / 螺旋素数

1からはじめて以下のように反時計回りに数字を並べていくと,辺の長さが7の渦巻きができる。

37363534333231
38171615141330
39185431229
40196121128
41207891027
42212223242526
43444546474849

面白いことに奇平方数が右下の対角線上に出現する。もっと面白いことに,対角線上の13個の数字のうち8個が素数である。割合は8/13 ≈ 62%である。

渦巻きに新しい層を付け加えよう。すると辺の長さが9の渦巻きができる。以下,この操作を繰り返していく。対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ。

Problem 58 - Project Euler


k 個目のうずまきの右下は (2k+1)^2。これから 2k, 4k, 6k 引いたものが左下,左上,右上の数です。(2k+1)^2 は素数でないことは明らかなので,他の3つについて調べます。うずまきが n 個あるとき,対角線上の数は 4n+1 個です。

最初はメモ化せずに f[n_]:= f[n - 1] + Total……としてしまい,「再帰が深すぎる」エラーに見舞われましたが,f[n]= を挿入するとすんなりいきました。