065. 自然常数的渐进(Convergents of e)

二的平方根可以写成如下无限连分数的形式:

$$ \sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}}} $$
这个无限连分数可以被记为\(\sqrt{2} = [1; (2)]\),其中\((2)\)表示2无限循环。类似的,我们可以把二十三的平方根记为\(\sqrt{23} = [4; (1, 3, 1, 8)]\)。可以发现,一个数平方根的无限连分数序列的部分值可以提供一个很好的有理数近似,让我们看一下\(\sqrt{2}\)的渐近表示:
$$ \begin{aligned} 1 + \dfrac{1}{2} &= \dfrac{3}{2}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2}} &= \dfrac{7}{5}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} &= \dfrac{17}{12}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} &= \dfrac{41}{29} \end{aligned} $$
因此\(\sqrt{2}\)前十个渐进表示的序列如下:
$$ 1, \dfrac{3}{2}, \dfrac{7}{5}, \dfrac{17}{12}, \dfrac{41}{29}, \dfrac{99}{70}, \dfrac{239}{169}, \dfrac{577}{408}, \dfrac{1393}{985}, \dfrac{3363}{2378}, ... $$
最令人惊奇的是自然常数也可以用无穷连分数表示:
$$ e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...] $$
自然常数\(e\)的渐进表示的前十项如下:
$$ 2, 3, \dfrac{8}{3}, \dfrac{11}{4}, \dfrac{19}{7}, \dfrac{87}{32}, \dfrac{106}{39}, \dfrac{193}{71}, \dfrac{1264}{465}, \dfrac{1457}{536}, ... $$
第十个渐进表示的分子各位数之和为\(1 + 4 + 5 + 7 = 17\)。求自然常数第一百项渐进表示分子的各位数之和。

分析:此题和上一题也就是第六十四题非常类似,都是考察连分数的相关知识。实际上,在这个维基页面非常系统的介绍了连分数的相关知识,我们这里关心的是如何从某个数的无穷边分数推导出相应的渐进表示。我们设某个无理数的无穷连分数表示第\(k\)项为\(a_k\),则对于自然常数的无穷连分数表示,我们有\(a_6=4,a_{10}=1\),则其渐进表示的第\(k\)项的分子为:

$$ n_k=a_k\cdot n_{k-1}+n_{k-2},\ where\ n_0=1,n_1=2 $$

因此在已知\(a_k\)的情况下,我们就可以推导出\(n_k\)。题目已经给出了自然常数的无穷连分数表示,我们发现其第三项、第六项以及所有整除三的项的为\(2k/3\),而除首项外的其它项则为一,根据这个规律我们可以计算出\(a_k\),从而计算出\(n_k\),然后计算其各位数之和,即为题目所求。代码如下:

# time cost = 30.8 µs ± 113 ns

def main(N=100):
    m,n = 1,2
    for i in range(2,N+1):
        a = 2 * i//3 if i%3==0 else 1
        m,n = n,m+a*n
    return sum(map(int,str(n)))