Project Euler 57「平方根の近似分数」

数学的考察はしてません。（トライはした）
3/2、7/5、17/12、41/29をジーっと眺めて法則性を探して、やってみたら正解だっただけ。
行けば分かるさの精神。

Problem 57 「平方根の近似分数」

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

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

最初の4回の繰り返しを展開すると以下が得られる.

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.
最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?

def hoge(num):
    def cnt():
        n, d = 1, 1
        for _ in range(num):
            n, d = n + d * 2, n + d
            yield len(str(n)) > len(str(d))
    return sum(cnt())

print(hoge(1000))

初めはこんなんやろうとしたけどMemoryErrorで早々に怒られた。

from fractions import Fraction

def hoge(num):
    def cnt():
        s = '1 + 1/2'
        for _ in range(num):
            F = Fraction(eval(s)).limit_denominator()
            numer, denom = str(F).split('/')
            yield len(numer) > len(denom)
            s = s.replace('1/2', '1/(2 + 1/2)')
    return sum(cnt())

print(hoge(1000))