Project Euler 321

发表于 2022-06-02 更新于 2023-07-03 分类于 Project Euler 阅读次数： 162 本文字数： 1.7k 阅读时长 ≈ 2 分钟

Project Euler 321

题目

Swapping Counters

A horizontal row comprising of $2 n + 1$ squares has $n$ red counters placed at one end and $n$ blue counters at the other end, being separated by a single empty square in the centre. For example, when $n = 3$ .

A counter can move from one square to the next (slide) or can jump over another counter (hop) as long as the square next to that counter is unoccupied.

Let $M (n)$ represent the minimum number of moves/actions to completely reverse the positions of the coloured counters; that is, move all the red counters to the right and all the blue counters to the left.

It can be verified $M (3) = 15$ , which also happens to be a triangle number.

If we create a sequence based on the values of n for which $M (n)$ is a triangle number then the first five terms would be: $1, 3, 10, 22,$ and $63$ , and their sum would be $99$ .

Find the sum of the first forty terms of this sequence.

解决方案

第一个问题： $M (n)$ 的式子是什么？

可以发现，每一枚筹码如果移动到它的目标格子，都需要前进 $n + 1$ 格，因此 $2 n$ 枚筹码就总共需要前进 $2 n (n + 1)$ 格子。

但是，当两个不同颜色的筹码相遇时，一个筹码就可以朝另一个筹码跳跃，一次操作就会前进 $2$ 格格子。这样的相遇一共会发生 $n^{2}$ 次。

因此， $M (n) = 2 n (n + 1) - n^{2} = n^{2} + 2 n$ 。

第二个问题：求解问题中要求的数。

如果 $M (n)$ 为三角数，设存在 m，使得 $n^{2} + 2 n = \frac{m (m + 1)}{2}$ 。

移项，两边同乘一个数 $8$ ，得到 $4 m (m + 1) - 8 (n^{2} + 2 n) = 0$

进行配方，移项后得到 $(2 m + 1)^{2} - 8 (n + 1)^{2} = - 7$ 。

令 $x = 2 m + 1, y = n + 1$ ，那么得到 $x^{2} - 8 y^{2} = - 7$ ，该类方程为广义佩尔方程： $x^{2} - D y^{2} = N$ 。

但是，广义佩尔方程的基础解有多个，不像 $N = 1, - 1$ 时的情形。

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

$(1, 1), (5, 2)$

使用与第 137 题类似的方法，每一组 $x^{2} - 8 y^{2} = - 7$ 的通解由它的一个基础解 $(x_{1}, y_{1})$ 和 $x^{2} - 8 y^{2} = 1$ 的通解 $(a_{k}, b_{k})$ 得到。

${\begin{aligned} x_{k + 1} = x_{1} a_{k} + D y_{1} b_{k} \\ y_{k + 1} = y_{1} a_{k} + x_{1} b_{k} \end{aligned}$

再根据第 66 题的算法，可以得到 $x^{2} - 8 y^{2} = 1$ 的通解： $a_{1} = 3, b_{1} = 1$ ${\begin{aligned} a_{k + 1} = 3 a_{k} + 8 b_{k} \\ b_{k + 1} = a_{k} + 3 b_{k} \end{aligned}$

计算出每一对 $(x, y)$ 后，需要回代 $m = \frac{x - 1}{2}, n = y - 1$ 。判断这时 $m, n$ 是否为正整数。最终求出这些 $n$ 的和

代码

N = 40


def gen_solution():
    D = 8
    base_sol = [(1, 1), (5, 2)]
    a, b = 3, 1
    for x, y in base_sol:
        yield x, y
    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, y
        a, b = 3 * a + 8 * b, a + 3 * b


ls = []
for x, y in gen_solution():
    if (x - 1) % 2 == 0 and (x - 1) // 2 > 0:
        ls.append(y - 1)
        if len(ls) == N:
            break
ans = sum(ls)
print(ans)