Project Euler 57

プロジェクトオイラー
http://projecteuler.net/index.php

Q57.
√2 = 1 + 1/(2 + 1/(2 + …
を途中で打ち切ったとき、
1 + 1/2 = 3/2
1 + 1/(2 + 1/2) = 7/5
などとなる。
これを10万回行ったとき、何回分母より分子の桁が大きくなるか

分子をa_n、分母をb_nと表すと、

a_n+1 / b_n+1 = 1 + 1 / (1 + a_n / b_n) = (a_n + 2b_n) / (a_n + b_n)

だから、

a₁ = 3
b₁ = 2
a_n+1 = a_n + 2b_n
b_n+1 = a_n + b_n

互いに素であることも容易にわかる。

from itertools import repeat
def get_digits(n):

    counter = 0

    while n:

        n /= 10

        counter += 1

    return counter
def gen_fraction():

    a = 3

    b = 2

    while True:

        yield [ a, b ]

        a, b = a + 2 * b, a + b
def is_diff_digits(f):

    return get_digits(f[0]) > get_digits(f[1])
N = 1000

g = gen_fraction()

print sum(map(is_diff_digits, map(lambda i: g.next(), range(N))))