It is possible to show that the square root of two can be expressed as an infinite continued fraction.
\[\sqrt{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.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?
平方根逼近
2的平方根可以用一个无限连分数表示：
\[\sqrt{2} = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...\]将连分数计算取前四次迭代展开式分别是：
\[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...\]接下来的三个迭代展开式分别是99/70、239/169和577/408，但是直到第八个迭代展开式1393/985，分子的位数第一次超过分母的位数。
在前一千个迭代展开式中，有多少个分数分子的位数多于分母的位数？
def process(level):
a, b = 3, 2
while level > 1:
a, b = a + 2 * b, a + b
level -= 1
return a, b
result = 0
for i in range(1, 1001):
a, b = process(i)
if len(str(b)) < len(str(a)):
result += 1
# print process(i)
print result
草稿：
\[1+1/(1+a/b) = (a+2b)/(a+b)\]其实是很早的就做了的题，觉得草稿肯定还有更多，没那么简单……