Project EulerのProblem 72(日本語)です。
072.rb
最初、Problem 71と同じような解き方で数を数えてみたのですが、さすがに1,000,000ともなると、stack level too deep (SystemStackError) が出ますね。最近、大きい数を扱うときは、そのままの解き方では解けないということにようやく気づいてきたので作戦変更です。
「ファレイ数列」を見てみると、数列の長さは、Problem 69, Problem 70で出てきたを使って求めることができるんですね*1。
*1:Wkipediaでは両端の0/1, 1/1を含んだ数を数えています。