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
pn / qn = [ a0; a1, a2, ..., an ]で表される連分数の展開は、
pn = pn-1 + an-1pn-2
qn = qn-1 + an-1qn-2
(n ≥ 2)
で計算できます。しかし、今回の場合は見て分かるように、
pn = pn-1 + 2qn-1
qn = pn-1 + qn-1
で表せます。上の漸化式を使って帰納法で示せます。
def num_digits(n):
num = 0
while n:
n /= 10
num += 1
return numdef gen_sqrt_2_approx(n):
num, den = 1, 1
for k in range(n):
num, den = num + den + den, num + den
yield num, dent = 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 kdef gen_sqrt_2_approx(n):
num, den = 1, 1
for k in range(n):
num, den = num + den + den, num + den
yield num, denN = 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
これでかなり速くなります。まだ工夫の余地はありますが。