2的平方根可以表示为如下无限连分数: $$\sqrt2=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \dots}}}$$ 这个连分数前四次展开依次是： \begin{align*} 1+\frac{1}{2}=\frac{3}{2}&=1.5, \\ 1+\frac{1}{2+\frac{1}{2}}=\frac{7}{5}&=1.4, \\ 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}=\frac{17}{12}&=1.41666\dots, \\ 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}}=\frac{41}{29}&=1.41379\dots, \end{align*} 接下来的三次展开得到的分别是$99/70$、$239/169$、$577/408$，直到第八次展开得$1393/985$，分子的位数才第一次超过分母的位数。

在前一千次展开中，有多少次满足分子的位数多于分母的位数？

本题难度:

解答

直接计算易得结果是$153$。

from fractions import Fraction as f

a=[f(1,2)]

for k in range(1,1000):a.append(f(1,2+a[-1]))

print sum(len(str((1+a[k]).numerator))>len(str((1+a[k]).denominator)) for k in range(1000))