HOME SUMMARY

Problem 28

1. Problem

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?

螺旋数阵对角线

从 1 开始,按顺时针顺序铺开的 5 * 5 螺旋数阵如下所示:

(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)

可以看出,该数阵对角线上的数之和是 101。

考虑以同样方式构成的 1001 * 1001 螺旋数阵,其对角线上的数之和是多少?

2. Solution

我们当然可以根据这个规律生成一个 1001 * 1001 的矩形,然后进行求和,但是既然能够推出公式,那就直接推公式吧,对于边长为 \(n (n \gt 1 \ \ n = 2k + 1)\) 的螺旋矩阵,它的四个角的值分别为:

\[\left\{\begin{align} &n^2 \notag \\ &(n-2)^2 + (n-1) \notag \\ &(n-2)^2 + 2(n-1) \notag \\ &(n-2)^2 + 3(n-1) \notag \end{align}\right.\ \ n \gt 1\]

将这四个值加起来的值为 \(4n^2 -6n + 6\),接着我们求值即可:

\[1 + \sum_{k=1}^{500}[4(2k+1)^2 - 6(2k+1) + 6]\]

(cl-do ((k 1 (1+ k))
        (sum 1 (+ sum (+ (* 4 (expt (1+ (* k 2)) 2))
                         (* -6 (1+ (* k 2)))
                         6))))
    ((> k 500) sum))
=> 669171001

当然,根据自然数求和以及自然数平方求和公式,我们也可以直接给出公式解:

\[\left\{\begin{align} \sum_{i=1}^{n}i &= \frac{n(n+1)}{2} \notag \\ \sum_{i=1}^{n}i^2 &= \frac{n(n+1)(2n+1)}{6} \notag \end{align}\right.\]

\[1 + 4\sum_{k=1}^{n}[4k^2 +k + 1] = \frac{16}{3}n^3 + 10n^2 + \frac{26}{3} + 1\]

(let ((n 500))
  (/ (+ (* 16 n n n) (* 30 n n) (* 26 n) 3) 3))
=> 669171001