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

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

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

Project EulerのProblem 58。

https://projecteuler.net/problem=58

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

f:id:keisukefukuda:20150530153945p:plain

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

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

{ \displaystyle
A_n = 4{n}^2 - 2n + 1
}

{ \displaystyle
B_n = 4{n}^2 + 1
}

{ \displaystyle
C_n = 4{n}^2 + 2n + 1
}

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

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

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

$ lein run -m euler.prob58/run

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

【広告】