028. 数字螺旋的对角线(Number spiral diagonals)

从一开始按顺时针方向向右移动并加一，形成的五乘五的数字螺旋如下：

可以验证对角线上的红色数字之和为101。对于一个1001乘以1001的同样的数字螺旋，其对角线上的值的和是多少？

分析：假设$n$表示数字螺旋的层数，如$n=0$即表示只有最中间一个数也就是1，此时的对角线数字之和即为1，记为$f(0)=1$。当$n=1$时形成一个$3\times3$的数字螺旋，$3=2\times1+1$并且右上角的数为$9=3^2=(2\times1+1)^2$。同理，当$n=2$形成一个$5\times5$的数字螺旋，右上角数字为$25=5^2=(2\times2+1)^2$。通过以上分析，我们可以总结出，要求一个$1001\times1001$的数字螺旋对角线数字之和，由于$1001=2\times500+1$，此时的数字螺旋共有500层，其右上角数字为$1001^2$。

一般地，假设我们要求一个$(2n+1)\times(2n+1)$的数字螺旋对角线数字之和，则右上角数字大小为$(2n+1)^2$，逆时针旋转其左上角数字为$(2n+1)^2-2n$，左下角数字为$(2n+1)^2-4n$，右下角数字为$(2n+1)^2-6n$，则可以推出$n$层的数字螺旋的对角线数字之和为：

$$ f(n)=4(2n+1)^2-12n+f(n-1) $$

因此我们可以推出$f(n)-f(n-1)=4(2n+1)^2-12n=16n^2+4n+4$，使用如下方法我们求得此递推公式的通项：

$$ \begin{aligned} f(n)-f(n-1)&=16n^2+4n+4\\ f(n-1)-f(n-2)&=16(n-1)^2+4(n-1)+4\\ \vdots\\ f(2)-f(1)&=16\times2^2+4\times2+4\\ f(1)-f(0)&=16\times1^2+4\times1+4 \end{aligned} $$

将上述等式相加则得：

$$ \begin{aligned} f(n)-f(0)&=\sum_{i=1}^{n}(16i^2+4i+4)\\ &=16\sum_{i=1}^{n}i^2+4\sum_{i=1}^{n}i+4\sum_{i=1}^{n}\\ &=\frac{16}{6}n(n+1)(2n+1)+\frac{4}{2}n(n+1)+4n\\ &=\frac{16}{3}n^3+10n^2+\frac{26}{3}n \end{aligned} $$

之前已设$f(0)=1$，则有：

$$ f(n)=\frac{16}{3}n^3+10n^2+\frac{26}{3}n+1 $$

题目要求$1001\times1001$的数字螺旋的对角线数字之和，此时$n=500$，代入公式$f(500)$即为所求。

def main(n=500):
    res = 16*n**3/3 + 10*n**2 + 26*n/3 + 1
    return int(res)

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页