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$个斐波那契金块。

\(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\)

分析：初看这是一道与无穷级数有关的问题，但敏感的同学可能发现，这里的无穷级数实际上是斐波那契数列的生成函数，关于什么是生成函数以及它的主要应用，这里不展开讨论，具体大家可以参见相关的文章与书籍。下面我们来看一下如何推导斐波那契数列的生成函数，我们把$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

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页