057. 平方根收敛(Square root convergents)

二的平方根可以表示为以下这个无穷连分数:

$$ \sqrt 2 =1+ \frac 1 {2+ \frac 1 {2 +\frac 1 {2+ \dots}}} $$
通过把前四项展开,我们得到:
$$ \begin{aligned} 1 + \frac 1 2 &= \frac 32 = 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{aligned} $$
接下来三项展开式为\(99/70,239/169\)\(577/408\),但是第八项是\(1393/985\),是第一个分子的位数超过分母的位数的例子。

求在前一千项展开式中,有多少分数的分子位数超过分母的位数?

分析:首先我们可以推导出上面的展开式中分子和分母的递推式:设\(a_k=n_k/d_k\)表示第\(k\)项展开式,则易知:

$$ a_{k+1}=1+\frac{1}{1+a_k}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{d_k+n_k}=\frac{2d_k+n_k}{d_k+n_k} $$

即对于第\(k+1\)项展开式,其分子为\(2d_k+n_k\),分母为\(d_k+n_k\)。因此我们可以根据这个递推关系计算每一项展开式的分子与分母,对其取以十为底的对数判断其位数,然后统计分子位数大于分母位数的项,即为题目所求。代码如下:

# time cost = 885 µs ± 9.93 µs

from math import log10

def main(N=1000):
    c,n,d = 0,1,1
    for i in range(N):
        n,d = 2 * d + n,d + n
        if int(log10(n)) > int(log10(d)):
            c += 1
    return c