0140 斐氏金块改
* * * *
拉格朗日计划
* * * *
斐氏金块改

考虑无穷级数 $$A_G(x)=G_1x+G_2x^2+G_3x^3+\ldots$$ 其中$G_k=G_{k-1}+G_{k-2}$具有和斐波那契数列相同的通项公式,但初值为$G_1=1, G_2=4$。

本题所考虑是的能令$A_G(x)$依次取到自然数$1,2,3,\ldots$的自然数x。 对每个自然数n,记$x_n$为满足$A_G(x_n)=n$的数,那么可以验证前五个这样的数依次是 $$\begin{matrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ \frac{\sqrt5-1}{4} & \frac{2}{5} & \frac{\sqrt{22}-2}{6} & \frac{\sqrt{137}-5}{14} & \frac{1}{2}\end{matrix}$$ 若$x_n$是有理数,则称n是斐波那契金块改,例如2是第一个斐波那契金块改。这样的数随着n的增加而越来越少,例如第二十个斐波那契金块是211345365。

求前30个斐波那契金块改之和。

本题难度:



解答

用与第137题相同的策略,可得 $$A(x)-xA(x)-x^2A(x)=3x^2+x,$$ 即 $$A(x)=\frac{3x^2+x}{1-x-x^2}.$$ 取 $$n=\frac{3x^2+x}{1-x-x^2},$$ 则有 $$(1+\frac{3}{n})x^2+(1+\frac{1}{n})x-1=0.$$ 从而欲使 $$x=\frac{-1-\frac{1}{n}\pm\sqrt{\frac{1}{n^2}+\frac{2}{n}+1+\frac{12}{n}+4}}{2+\frac{6}{n}}=\frac{-n-1\pm\sqrt{1+14n+5n^2}}{2n+6},$$ 为有理数,则需要$1+14n+5n^2$为完全平方数。注意到 $$5n^2+14n+1=m^2 \Leftrightarrow 5(n+\frac{7}{5})^2-\frac{44}{5}=m^2 \Leftrightarrow (5n+7)^2-5m^2=44.$$ 从而需要计算类Pell方程$x^2-5y^2=44$的满足$x\ge 12$以及$x\bmod 5=2$的解。

若$x,y$是其一组解,而$u,v$是$u^2-5v^2=1$的一组解,则由 $$(u x + d v y)^2 - d(v x + u y)^2 = (u^2 - d v^2) (x^2 - d y^2)$$ 就可递推生成另外的解。不过与等式右侧为$1$的Pell方程的情形不同,此种方程的解可以有多个轨道,所以需要找到所有轨道的生成元才能生成全部解集。

对本题而言总共有六个轨道,可以参考Math Stackexchange的这个帖子这个帖子

结果是$5673835352990$。

r=[[0,296],[2,1050],[5,2037],[21,7205],[42,13970],[152,49392]]

for i in range(3):
    for d in r:
        d.append(322*d[-1]-d[-2]+448)

print sum(sum(d) for d in r)+322*r[0][-1]-r[0][-2]+448