projecteuler28-螺旋方阵对角线的和

2017-08-09

Number spiral diagonals

Problem 28

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?

这个题目拿到可以用朴素的循环法做，后面会给出代码，当然如果这个矩阵极大的时候，一层循环也是消耗时间的，那是不是应该考虑更好的方法，下面给出数学公式的推导

很容易看出每一圈上的四个数字，左上角+左下角 = 右上角+右下角的

那么我们只要求出一边即可

考虑求右下角数字的和

3 = 1+2

13 = 1+2+10

31 = 1+2+10+18

好像是有规律的

我们令

f(1)=3 , f(2)=13, f(3)=31 …

可以发现因为在右下角，所以当前的f(i)所对应的是在2∗i+1的矩阵上，经历了这个环上走过3条棱，棱长为2∗i，下一个环上走了一条棱，棱长为2∗i+2

那么f(i+1) = f(i) + 2∗i∗3+2∗i+2 = f(i) + 8∗i + 2
$$
f(n+1) = 3 + \sum_{i=1}^{n}{8∗i + 2} = 4n(n+1) + 2n + 3 = 4n^2+6n+3 \\
f(n) = 4(n-1)^2+6(n-1)+3 = 4n^2-2n+1
$$
那我们需要求解的是所有f(x)的和F(x)
$$
F(n) = \sum_{i=1}^{n}{f(n)} = \sum_{i=1}^{n}{4n^2-2n+1} \\
=\sum_{i=1}^{n}{4n^2}-\sum_{i=1}^{n}{2n}+\sum_{i=1}^{n}{1} \\
=4∗1/6n(n+1)(2n+1)-n(n+1)+n \\
=2/3n(n+1)(2n+1)-n(n+1)+n
$$

同理可以求解左上角

g(1) = 9 = 1+8

g(2) = 25 = 1+8+16

g(3) = 49 = 1+8+16+24

根据f(n)同样理解，对于g(i)来说，右上角是最大的数，接下来直接进入下一个环，棱长为2∗i+2，要经过全部四条棱，所以

g(i+1) = g(i)+4∗(2∗i+2)
$$
g(n+1) = 9 + \sum_{i=1}^{n} {8i+8} = 9+8n+4(n+1)n = 4n^2+12n+9 \\
g(n) = 4(n-1)^2+12(n-1)+9 = 4n^2+4n+1
$$
那么求所有g(i)的和的函数G(n)定义如下：
$$
G(n) = \sum_{i=1}^{n}{g(n)} = \sum_{i=1}^{n}{4n^2+4n+1} \\
=2/3∗n(n+1)(2n+1) + 2n(n+1)+n
$$
那么最后的结果就是(F(n)+G(n))*2+1,按照题目要求n=(1001-1)/2=500

# euler28
def number_spiral_diagonals(n):
    res = 1
    cur = 1
    for i in range(3, n+1, 2):
        res += cur*4 + (i-1)*10
        cur = cur + (i-1)*4
    return res
def F(n):
    return 2*n*(n+1)*(2*n+1)/3 - n*(n+1)+n
def G(n):
    return 2*n*(n+1)*(2*n+1)/3 + 2*n*(n+1)+n
print number_spiral_diagonals(1001) # 最朴素的方法
print F(2)," ",G(2)
print (F(500)+G(500))*2+1