Project Euler 140

题目

Modified Fibonacci golden nuggets

Consider the infinite polynomial series $AG(x) = x G_1 + x^2 G_2 + x^3 G_3 + \cdots$, where $G_k$ is the $k$th term of the second order recurrence relation $G_k = G{k-1} + G_{k-2}$, $G_1 = 1$ and $G_2 = 4$; that is, $1, 4, 5, 9, 14, 23, \dots$ .

For this problem we shall be concerned with values of $x$ for which $A_G(x)$ is a positive integer.

The corresponding values of $x$ for the first five natural numbers are shown below.

$x$	$A_G(x)$
$\dfrac{\sqrt{5}-1}{4}$	$1$
$\dfrac{2}{5}$	$2$
$\dfrac{\sqrt{22}-2}{6}$	$3$
$\dfrac{\sqrt{137}-5}{14}$	$4$
$\dfrac{1}{2}$	$5$

We shall call $A_G(x)$ a golden nugget if $x$ is rational, because they become increasingly rarer; for example, the 20th golden nugget is $211345365$.

Find the sum of the first thirty golden nuggets.

解决方案

和137题一样，有

$$\begin{aligned} A_G(x) & =xG_1+ & x^2G_2+x^3G_3+\dots \\ xA_G(x) & = & x^2G_1+x^3G_2+\dots\\ (1+x)A_G(x) &=xG_1+ &x^2G_3+x^3G_4+\dots\\ \end{aligned}$$

可以发现，第三条式子用了定义：$G_n=G_n-1+G_n-2$。

将$A_F(x)$代入第三条式子右侧，有：

$$(1+x)A_G(x)=xG_1+\dfrac{A_G(x)}{x}-G_1-xG_2$$

代入$G_1=1,G_2=4$，化简后，有：

$$A_G(x)=\dfrac{3x^2+x}{1-x-x^2}$$

令$A_F(x)=n$，$n$是一个正整数，有：$3x^2+x=n(1-x-x^2)$

化成关于$x$的一元二次方程，有$(n+3)x^2+(n+1)x-n=0$

如果$x$是一个有理数，那么其判别式$\Delta$必须是有理数。也就是$(n+1)^2-4n^2=5n^2+2n+1$必须是一个平方数。

如果方程的解$x$是一个有理数，那么其判别式$\Delta$必须是有理数。也就是$(n+1)^2+4n(n+3)=5n^2+14n+1$必须是一个平方数。

因此，令正整数$y$满足$y^2=5n^2+14n+1$。

两边同乘$5$，并配方，得$25n^2+70n+49-44=m^2$

移项，得：$(5n+7)^2-5y^2=44$

令$x=5n+7$，那么得到$x^2-5y^2=44$。这种广义佩尔方程和137题不同的是，后面的$N$变成$44$了。

经过一定范围的搜索，发现这个方程有$6$个基本解：

$(7,1),(8,2),(13,5),(17,7),(32,14),(43,19)$

使用与第137题类似的方法，每一组$x^2-5y^2=44$的通解由它的一个基础解$(x_1,y_1)$和$x^2-5y^2=1$的通解$(a_k,b_k)$得到。

$$\left \{\begin{aligned} & x_{k+1}=x_1a_k+Dy_1b_k\\ & y_{k+1}=y_1a_k+x_1b_k \end{aligned}\right.$$

将求出的$x$回代$n=\dfrac{x-7}{5}$。第$15$小的正整数$n$为所求。

代码

N = 30


def gen_solution():
    D = 5
    base_sol = [(7, 1), (8, 2), (13, 5), (17, 7), (32, 14), (43, 19)]
    a, b = 9, 4
    for x, y in base_sol:
        yield x
    while True:
        for i in range(len(base_sol)):
            x, y = base_sol[i]
            x, y = x * a + D * y * b, x * b + y * a
            yield x
        a, b = 9 * a + 20 * b, 4 * a + 9 * b


ls = []
for x in gen_solution():
    if (x - 7) % 5 == 0:
        w = (x - 7) // 5
        if w > 0:
            ls.append((x - 7) // 5)
    if len(ls) == N:
        break

ans = sum(ls)
print(ans)