Project Euler #57 - square root convergents

프로젝트 오일러 57번 - 루트2의 전개
sqrt(2) = 1 + 1 / ( 2 + 1 / ...) 로 전개할 수 있다. 무한전개를 하나씩 끊어서 풀면,
3/2
7/5
17/12
41/29
99/70
...
이렇게 된다. 1000번까지 전개해 보면서 분자와 분모의 자리수가 다른 경우는 몇 번인지 세어 본다.

계산해 보면(또는 관찰해 보면),
뒷분모 = 앞분자+앞분모
뒷분자 = 뒷분모+앞분모

그러면 찾는 것이 어렵지 않다.

n, d, cnt = 3, 2, 0
for i in range(2,1001):
    d, n = d+n, d+d+n
    if len(str(d)) < len(str(n)): cnt += 1

print cnt