Project Euler 28

题目

Number spiral diagonals

Starting with the number $1$ and moving to the right in a clockwise direction a $5$ by $5$ spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is $101$. What is the sum of the numbers on the diagonals in a $1001$ by $1001$ spiral formed in the same way?

解决方案

容易观察到，从里面向外，每一个圈都会比里面的一个圈多 $8$ 个元素。（以上图为例，第 $1$ 个圈为 $1$，第 $2$ 个圈为 $2\sim 9$，第 $3$ 个圈为 $10\sim 25$）。

因此，在第 $n$ 个圈中，四个角上的数可以分别用一个二次多项式 $p(n)=a{n}^2+bn+c$ 来定义这个通项公式。

这里不再详细计算。

通过 OEIS 查询，可以发现：

右下角的通项公式为 A054554，$4n^2-10n+7$;

左下角的通项公式为 A053755，$4(n-1{)}^2+1$;

左上角的通项公式为 A054569，$4n^2-6n+3$;

右上角的通项公式为 $(2n-1{)}^2$.

因此可以直接取所有值相加。

也可以再用平方和公式进一步导出结果：${\displaystyle \frac{2}{3}}(8n^3-9n^2+7n)-3$

代码

NOTE: 本代码只适用于矩阵大小为奇数时的情况。

N = 1001
ans = 0

# 1~N/2+1：从内向外的圈数。
for i in range(1, N // 2 + 2):
    ans += 4 * i * i - 10 * i + 7
    ans += 4 * (i - 1) * (i - 1) + 1
    ans += 4 * i * i - 6 * i + 3
    ans += (2 * i - 1) ** 2
# 中心点算重复了3次，故减去。
ans -= 3
print(ans)

N = 1001
N = N // 2 + 1
ans = (8 * N ** 3 - 9 * N ** 2 + 7 * N) * 2 // 3 - 3
print(ans)