Problem 28: Number spiral diagonals

Problem:

Please find the problem here.

Solution:

Since 1001² is small, I could have just fill the spiral and compute the sum. In fact, that is how I got the answer accepted for the first time. But I decide this is a chance for me to do some math, and so I do.

First notice the spiral (except the initial 1) can be decomposed into "Shells", each shell starts with the upper right corner and ends with a perfect square at the upper left corner. The values at the corners forms an arithmetic progression with common difference 2 * i, where i is the shell number, starting from 1.

With that observation, it is easy to translate that to the code below.

Apparently, the code can be further simplified, but I am not doing that in the code for simplicity.

Using Matlab, we can simplify this quickly using the commands below

clear
syms i
e = (2 * i + 1)^2
d = 2 * i
s = e - 3 * d
t = (s + e) * 4 / 2
expand(t)

Now t = 16i²+4i+4 is the term for summation, given the summation formula, we can even sum them up directly as follow

clear
syms n
q = n * (n + 1) * (2 * n + 1) / 6
l = n * (n + 1) / 2
o = 16 * q + 4 * l + 4 * n + 1
expand(o)

That gives the overall sum formula to be 16/3*n^3+10*n^2+26/3*n+1, an amazing simple cubic equation.

Code:

namespace Euler

{
    using System;

    internal static partial class Program
    {
        public static void Problem028()
        {
            long sum = 1;
            for (int i = 1; i < (1001 + 1) / 2; i++)
            {
                long end = (2 * i + 1) * (2 * i + 1);
                long diff = 2 * i;
                long start = end - 3 * diff;
                sum += (start + end) * 4 / 2;
            }
            Console.WriteLine(sum);
        }
    }
}

Answer: 669171001