Euler project57(Python 0.003015)

It is possible to show that the square root of two can be expressed
 as an infinite continued fraction.
(２の平方根は無限連分数として表すことができる。)

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

By expanding this for the first four iterations, we get:
(最初の４回の繰り返しを展開すると次が得られる。)

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...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 
1393/985, is the first example where the number of digits in the numerator
 exceeds the number of digits in the denominator.
(次の３つの項は99/70, 239/169,577/408であるが、
分子の桁が分母の桁を越える最初の項は８項の1393/985である。)

In the first one-thousand expansions, how many fractions
 contain a numerator with more digits than denominator?
（最初の１０００項の内、分子の桁が分母の桁を越える分数はいくつだろうか？）

解法：
wikipedia: 連分数の性質から容易に求めることができる。

#-*- coding:utf-8 -*-

import math
from datetime import datetime

def Euler57():
	P = [1, 1]
	Q = [0, 1]
	A = [1]
	[A.append(2) for i in xrange(999)]
	count = 0
	for i in xrange(2,1000):
		p = A[i-1]*P[i-1]+P[i-2]
		q = A[i-1]*Q[i-1]+Q[i-2]
		P.append(p)
		Q.append(q)
		if int(math.log10(p)) > int(math.log10(q)):
			count += 1
	return count

def main():
	start = datetime.now()
	answer = Euler57()
	end = datetime.now()
	print end - start, answer

if __name__ == "__main__":
	main()