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

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

IMG

可以验证对角线上的红色数字之和为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)