PamGau

Problem 58 (Project Euler) [原文]

1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

(中略)

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

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

Problem 28で扱った螺旋数列の問題で、手間が省けて簡単かと思いきや、さすがにこのレベルの問題はひとひねりがあります。

「エラストテネスの篩」はせいぜい400万ぐらいまでを用意すればよかろうと思ったら、篩で用意した素数の範囲を超えても、なかなか10%を割りません。

5千万ぐらいまで確保しようとしたところで、当然のことながら、必要なメモリ領域を確保できなくなりました。

やむなく「ミラー・ラビン」でググると、親切にもWikipediaに素数判定用のRubyコードがあったのでコピペしました。敗北感にまみれながら…orz

ミラー-ラビン素数判定法 (Wikipedia)

Problem 57 (Project Euler) [原文]

2の平方根は無限に続く連分数で表すことができる.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

(中略)

第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?

とりあえず、連分数部分の分母・分子の数列をそれぞれ a_n, b_n とすると、以下の漸化式が成立します。

• a_n = 2a_n-1 + b_n-1, a₁ = 2
• b_n = a_n-1, b₁ = 1

プログラムで漸化式を扱う場合、そのまま関数にすると再帰呼び出しによる再計算量が異常に多くなり、実行効率が激減します。

メモリを上手に使うのがうまいやりかたでしょう。

  seq_a = [2] # 分母
  seq_b = [1] # 連分数部分の分子
  ans = 0       # カウンタ

  (1..1000).each do |i|
    seq_a << seq_a[i-1] * 2 + seq_b[i-1]
    seq_b << seq_a[i-1]
    ans += 1 if seq_a[-1].to_s.length < (seq_a[-1] + seq_b[-1]).to_s.length
  end
  puts ans