1から順に数字を半時計回りに並べていくと奇数の二乗の長さの正方形を順に作ることができる。このときに、対角線に現れる数のうちの素数の割合が10%を下回るのは、正方形の一辺の長さがいくつになったときか。
原理的には難しくない。数字を規則的に並べると、殆どの場合はどの場所にどの数字が来るかを簡単な式で表現することができる。今回であれば、右下の対角線には奇数の二乗((2k+1)2)が並ぶ(よって素数は現れない)ことがすぐ分かり、各頂点の数字もそこから時計回りに 2k ずつ引いた数になる。今回の問題では頂点以外は興味がないから、知るべきことはこれで全てである。
なので、数字の並びが一周するごとに左下、左上、右上の3つの数を調べ、素数ならカウントアップしていく。一方で一周するごとに数字は当然4つずつ増えていくことになるから、総数は4ずつ増加する。これをずっと追いかけていって、素数が10%を下回ったところでストップ。
割合を計算する際に、毎回足し算で総数を求めると計算量が膨大になるので、一周前の結果を使ってやらないと計算が終わらない(実験済み)。
数字並べ☆