Project Euler 57

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回の展開で、分子の桁数が分母の桁数を超える分数はいくつあるか。
http://projecteuler.net/index.php?section=problems&id=57

p_n / q_n = [ a₀; a₁, a₂, ..., a_n ]で表される連分数の展開は、

p_n = p_n-1 + a_n-1p_n-2
q_n = q_n-1 + a_n-1q_n-2
(n ≥ 2)

で計算できます。しかし、今回の場合は見て分かるように、

p_n = p_n-1 + 2q_n-1
q_n = p_n-1 + q_n-1

で表せます。上の漸化式を使って帰納法で示せます。

def num_digits(n):

    num = 0

    while n:

        n /= 10

        num += 1

    return num
def gen_sqrt_2_approx(n):

    num, den = 1, 1

    for k in range(n):

        num, den = num + den + den, num + den

        yield num, den
t = time.clock()

N = 1000

print sum(map(lambda x: num_digits(x[0]) > num_digits(x[1]),

                                        gen_sqrt_2_approx(N)))

桁数を求めるのは上のようでもいいのですが、桁数は一つずつしか増えていかないので次のようにも書けます。

def num_digits(n, k):

    m = 10 ** k

    if m < n:

        return k + 1

    else:

        return k
def gen_sqrt_2_approx(n):

    num, den = 1, 1

    for k in range(n):

        num, den = num + den + den, num + den

        yield num, den
N = 1000

digits = 1

counter = 0

for num, den in gen_sqrt_2_approx(N):

    digits_num = num_digits(num, digits)

    digits_den = num_digits(den, digits)

    if digits_num > digits_den:

        counter += 1

    digits = digits_num

print counter

これでかなり速くなります。まだ工夫の余地はありますが。