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\sim9$，第$3$个圈为$10\sim25$）。

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

这里不再详细计算。

通过OEIS查询，可以发现：

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

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

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

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

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

也可以再用平方和公式进一步导出结果：$\dfrac{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)