Project Euler Problem 58「Spiral Primes 螺旋素数」

Project EulerのProblem 58。

https://projecteuler.net/problem=58

まず、下の図のように、第ｎ週目の四隅の数値を右上から反時計回りに , , , とおく。また、第ｎ週の正方形の一辺の長さは2nであることにも注意。（注：編の長さというのは微妙な言い方だが、数値の個数でなくて幅と考えてください）

このとき、まず右下の数値の を見てみると、問題文でも触れられているとおり、平方数になる。これは、正方形の一辺の長さが2nであることに注意しながらとの漸化式を作って一般項を求め、平方完成すれば の形で表現できることがわかる。

さて、さらにから螺旋を戻ることによって、, , はそれぞれ以下のように表すことができる。

というわけで、これでｎ週目の角に現れる数値をすべて直ちに計算できることになったので、nについて順番に繰り返しながら、素数の数 / 数の素数 の比率を計算していけば良い。

いままではコードはPythonで書いていたのだが、今回からClojureで書くことにした。

euler/prob58.clj at master · keisukefukuda/euler · GitHub

$ lein run -m euler.prob58/run

として走らせると、n=13120 の時に 比率≒0.0999981 < 0.1 となる。（答えはnそのものではないので注意）