Problem 28 : Number Spiral Diagonals

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?

                                                                                                       (https://projecteuler.net/problem=28)

There are LOTS of possible solutions for this problem.

I will suggest you two of them, including my own and the good one I found online and in the forum.

1) Algorithmic approach using iteration

This is most computer-science-ish solution I can come up with, as I didn't use my brain at all while writing this solution. If you look at the second solution, you will see what I mean.

Let's look at the red numbers and the distance between them.

In the center, it's 1. Okay, we get that.

In the second layer, where the numbers 2 - 9 are located, we see that the difference between the number is 2. Keep that in mind.

In the third layer, where the numbers 10 - 25 are located, we see that the difference between the number is 4.

In the fourth layer..? the difference will be 6. A simple arithmetic progression -> 2n, where n ≥ 1

So from this, we know that we need to:

1) find the incrementation for each layer and
2) increase the number by the incrementation x 4 (four corners) and add them to our total sum

Here is the implementation:

private static final int LEN = 1001;

    public static void run()
    {
        int currentNum = 1;
        int sum = currentNum;
        
        for (int i = 1; i <= LEN/2; i++)
        {
             int incr = 2*i;
             for (int j = 0; j < 4; j++) // calculate all 4 sides
             {
                  currentNum += incr;
                  sum += currentNum;
              }
        }
        System.out.println(sum);
}

2) Mathematical approach using universal formula

I found this solution in: http://www.mathblog.dk/project-euler-28-sum-diagonals-spiral/

Kristian explained his logic really well, but I will briefly go over his solution.

The most gorgeous part of his solution is that we don't need any computer algorithm to solve this problem.

We can manually find the total sum of red numbers for L x L square:

n	0	1	2	3	4	5	6
f(n)	1	25	101	261	537	961	1565
∆1		24	76	160	276	424	604
∆2			52	84	116	148	180
∆3				32	32	32	32

where n = [L / 2]

Because ∆₃ has all the constant incrementation, we will use 3rd-order polynomial function.

f(n) = ax³ + bx² + cx + d

We will use the following four equations to find the four constants a, b, c, and d:

d = 1

a + b+ c + d = 25

8a + 4b + 2c + d = 101

27a + 9b + 3c + d = 261

After solving the equations:

a = 16/3, b = 10, c = 26/3, d = 1

So our final formula is:

f(n) = 16/3x³ + 10x² + 26/3x + 1

If we plug in n = [L / 2] = [1001 / 2] = 500,

f(n) = f(500) = f(n) = 16/3(500)³ + 10(500)² + 26/3(500) + 1 = 669171001

Answer is 669171001
Execution time is .692364 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem028.java