137. 斐波那契金块(Fibonacci golden nuggets)

考虑无穷级数\(A_F(x) = x F_1 + x^2 F_2 + x^3 F_3 + \dots\),其中\(F_k\)是斐波那契数列的第\(k\)项,也就是说\(F_k = F_{k-1} + F_{k-2},F_1=1,F_2=1\)

在这个问题中,我们感兴趣的是那些使得\(A_F(x)\)为正整数的\(x\),奇怪的是:

$$ \begin{align*} A_F(\tfrac{1}{2}) &= (\tfrac{1}{2})\times 1 + (\tfrac{1}{2})^2\times 1 + (\tfrac{1}{2})^3\times 2 + (\tfrac{1}{2})^4\times 3 + (\tfrac{1}{2})^5\times 5 + \cdots \\ &= \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{2}{8} + \tfrac{3}{16} + \tfrac{5}{32} + \cdots \\ &= 2 \end{align*} $$
对应于前五个自然数的\(x\)如下所示:

\(x\) \(A_F(x)\)
\(\sqrt{2}-1\) \(1\)
\(\frac{1}{2}\) \(2\)
\(\frac{\sqrt{13}-2}{3}\) \(3\)
\(\frac{\sqrt{89}-5}{8}\) \(4\)
\(\frac{\sqrt{34}-3}{5}\) \(5\)

\(x\)是有理数时,我们称\(A_F(x)\)是一个斐波那契金块,因为这样的数将会变得越来越稀少,例如,第\(10\)个斐波那契金块将是\(74049690\)。求第\(15\)个斐波那契金块。

分析:初看这是一道与无穷级数有关的问题,但敏感的同学可能发现,这里的无穷级数实际上是斐波那契数列的生成函数,关于什么是生成函数以及它的主要应用,这里不展开讨论,具体大家可以参见相关的文章与书籍。下面我们来看一下如何推导斐波那契数列的生成函数,我们把\(A_F(x)\)左右同时乘以\(x\)\(x^2\),并将相同次数的项对齐并依次相减:

$$ \begin{array}{ c r l c c } A_{F}( x) & = & xF_{1} + & x^{2} F_{2} + & x^{3} F_{3} +\cdots \\ xA_{F}( x) & = & & x^{2} F_{1} + & x^{3} F_{2} +\cdots \\ x^{2} A_{F}( x) & = & & & x^{3} F_{1} +\cdots \\ \left( 1-x-x^{2}\right) A_{F}( x) & = & 1x+ & 0x^{2} + & 0x^{3} +\cdots \end{array} $$

则显然有:

$$ A_{F}( x) =\frac{x}{1-x-x^{2}} $$

根据上式我们根据给定的\(x\)计算出无穷级数\(A_F(x)\)的和,如当\(x=1/2\)时有\(A_F(x)=2\),正是题目中给出的数值。根据题意,要求\(A_F(x)\)为正整数时的\(x\),且\(x\)须为有理数,则设:

$$ \frac{x}{1-x-x^{2}} =n\Rightarrow x=n-nx-nx^{2} \Rightarrow nx^{2} +( n+1) x-n=0 $$

\(n\)为正整数时,解以上一元二次方程,则有:

$$ x=\frac{-( n+1) +\sqrt{( n+1)^{2} +4n^{2}}}{2n} $$

要使得\(x\)为有理数,则根号中的数字必须为完全平方数,设其为\(m^2\),则有:

$$ ( n+1)^{2} +4n^{2} =m^{2} \Rightarrow n^{2} +2n+1+4n^{2} =m^{2} \Rightarrow 5n^{2} -m^{2} +2n+1=0 $$

则我们要求上述二元二次不定方程的正整数解,则经过适当变换可得:

$$ 25n^{2} +10n+1=5m^{2} -4\Rightarrow ( 5n+1)^{2} -5m^{2} =-4 $$

如果令\(x=5n+1,y=m\),则上式变为:

$$ x^2-5y^2=-4 $$

上述方程与佩尔方程非常相似,唯一的区别就方程右边不是\(1\)而是\(-4\),这种方程我们通常称之为广义佩尔方程(Generalized Pell's equation)。广义佩尔方程的求解比狭义佩尔方程和负佩尔方程更为复杂,主要的区别在于如果广义佩尔方程有解,则可以有多个基本解,而不像狭义佩尔方程与负佩尔方程那样只有一个基本解。目前常用的一种求解方法是\(LMM\)算法,这种方法由拉格朗日最早发现,并经后来的研究者加以完善,其基本原理仍与无理数的连分数表示有关。在这里我无法详细的描述这种方法,具体大家可以参见这篇文献

可以证明,如果广义佩尔方程有解,则其有无穷多组解,各个解之间存在着递推关系。假设\((x_0,y_0)\)为广义佩尔方程\(x^2-dy^2=n\)的一个基本解,则我们把方程\(u^2-dv^2=1\)称为上述广义佩尔方程的一个预解式,它的一个解为\((u_n,v_n)\),则根据恒等式:

$$ {\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2},} $$

我们有:

$$ {\displaystyle (x_{0}^{2} -dy_{0}^{2} )(u_{n}^{2} -dv_{n}^{2} )=(x_{0} u_{n} +dy_{0} v_{n} )^{2} -d(x_{0} v_{n} +u_{n} y_{0} )^{2} =n} $$

则有\(({\displaystyle x_{0} u_{n} +dy_{0} v_{n} ,x_{0} v_{n} +u_{n} y_{0})}\)也构成方程\(x^2-dy^2=n\)的一组解。因此只要我们求得了广义方程的基本解,就可以根据上述递推关系找到它更多的解。

回到题目本身,可验证方程\(u^2-5v^2=1\)的基本解是\((9,4)\),而方程\(x^2-5y^2=-4\)有三组基本解,分别为\((-1,1),(1,1),(4,2)\),我们可以基本解把方程的解分为三组,三组解分别满足不同的递推关系,对于基本解为\((-1,1)\)的解,其递推关系为:

$$ x_{n+1}=-u_n+5v_n,y_{n+1}=-v_n+u_n $$

当基本解为\((1,1)\)时,其递推关系为:

$$ x_{n+1}=u_n+5v_n,y_{n+1}=v_n+u_n $$

当基本解为\((4,2)\)时,其递推关系为:

$$ x_{n+1}=4u_n+10v_n,y_{n+1}=4v_n+2u_n $$

使用以上三个递推关系,我们就可以推出原方程更多的解并检验\(x\equiv1(mod\ 5)\)是否成立,如果成立则\((x-1)/5\)就是一个斐波那契金块,下表中最右侧三列列出了前十二个:

微信图片_20210518155340

只要再往下做递推,就不难发现第十五个斐波那契金块,求解的代码如下:

# time cost = 13.2 µs ± 128 ns

def main(N=15):
    arr = []
    x1,y1,x2,y2,x3,y3 = -1,1,1,1,4,2
    u,v = 9,4
    while True:
        x1,y1 = -u+5*v,-v+u
        x2,y2 = u+5*v,v+u
        x3,y3 = 4*u+10*v,4*v+2*u
        target = [(x-1)//5 for x in [x1,x2,x3] if (x-1)%5==0]
        arr += target
        if len(arr) == N:
            return arr[-1]
        else:
            u,v = 9*u+20*v,4*u+9*v