Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

Problem 72

Project EulerProblem 72(日本語)です。

072.rb

最初、Problem 71と同じような解き方で数を数えてみたのですが、さすがに1,000,000ともなると、stack level too deep (SystemStackError) が出ますね。最近、大きい数を扱うときは、そのままの解き方では解けないということにようやく気づいてきたので作戦変更です。
ファレイ数列」を見てみると、数列の長さは、Problem 69, Problem 70で出てきた\varphi(n)を使って求めることができるんですね*1


|F_n|=1\,+\,\sum_{m=1}^{n}\varphi(m)

*1:Wkipediaでは両端の0/1, 1/1を含んだ数を数えています。