のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 73

分母が12,000以下の既約分数は1/3と1/2の間にいくつあるか。


いくつかの方法を試すが計算が終わらない。これは例によって「知らないと解けない」系ではないかと疑い周辺情報を調べた結果、"Farey sequence"という有名な数列に関する問題であることが判明。それだけでもやられた感があるが、このFarey sequenceが非常に興味深い。この数列の性質と問題の解法はむちゃくちゃ深い。超高速アルゴリズムもありそうだ。

今回はそこまで掘り下げる力がなかったので、隣り合う2数から次の数を求めるアルゴリズムwikipediaから拝借してお茶を濁す(日本語版にはこのアルゴリズムは載っていない)。はっきり言って敗北感しかないのである。
それでも第2項が4000/11999になることは自力で計算した。

数学の深淵を見た…★★★