GilgaLab

Project Euler – Problem 28

Alright!
I have been away for a while as there are too many things happening right now and I have been pretty busy.
Well, this time I will resolve Problem 28 from Projet Euler. For this, I will use mostly a manual method for deducing the formulas and then a small C program to finish the sum for us :)
The problem states:

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?

According to the problem for this spiral the sum is 101 because: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25 = 101
Good! So in order to resolve this problem all we have to do is figure out what are the rules that guide the diagonal numbers.

I have divided this spiral in 4 diagonals:

• Center to right upper corner
• Center to right lower corner
• Center to left lower corner
• Center to left upper corner

If we expand this spiral a a little bit more, we will have:

73 74 75 76 77 78 79 80 81
72 43 44 45 46 47 48 49 50
71 42 21 22 23 24 25 26 51
70 41 20 07 08 09 10 27 52
69 40 19 06 01 02 11 28 53
68 39 18 05 04 03 12 29 54
67 38 17 16 15 14 13 30 55
66 37 36 35 34 33 32 31 56
65 64 63 62 61 60 59 58 57

Based on this we can deduce the formulas that generates each diagonal.

1. Center to right upper corner (1, 9, 25, 49, 81, ...)

For this one, we can see that for each level that expands, we have a squared number. So if we put a little bit of thinking on it, we can come up with the following formula:

Where n is the number of the line counting from the center up (The first line being 0)
You can try it!

2. Center to right lower corner (1, 3, 13, 31, 57, ...)

Comparing the results from the center to right upper corner results, we notice that the value here is the same as that diagonal minus 6*n. So the formula goes:

Where n is the number of the line counting from the center down (The first line being 0)
You can try it!

3. Center to left lower corner (1, 5, 17, 37, 65, ...)

Comparing the results from the center to right upper corner results, we notice that the value here is the same as that diagonal minus 4*n. So the formula goes:

Where n is the number of the line counting from the center down (The first line being 0)
You can also try this one!

4. Center to left upper corner (1, 7, 21, 43, 73, ...)

Comparing the results from the center to right upper corner results, we notice that the value here is the same as that diagonal minus 2*n. So the formula goes:

Where n is the number of the line counting from the center up (The first line being 0)
And once again you can try this one!

Now we need to figure out from what value to what value our 'n' should range. We know the following about our grid:

• When the grid is 3x3, we have 9 (3^2) at the right top corner
• When the grid is 5x5, we have 25 (5^2) at the right top corner
• When the grid is 7x7, we have 49 (7^2) at the right top corner
• When the grid is 9x9, we have 81 (9^2) at the right top corner
• When the grid is 1001x1001, we have 1002001 (1001^2) at the right top corner

Based on this we can conclude that we will have 500 lines up, 500 lines down and one line in the center, each line with 1001 rows.
Our sums should look like this then:

We calculate them all and sum them all together. After this is done, we subtract 3 from the sum because in them all we have added the element in the middle of the grid (1), so we have summed the number 1 four times, and the exercise asks us to sum all the numbers in the diagonals, meaning we should add each one of them only once.
We can than use WolframAlpha to calculate this sum, or just write a simple C code for it:

#include <stdio.h>
 
int main()
{
    int n;
    unsigned long long sum = 0;
 
    for(n = 0; n <= 500; n++)
    {
        sum += ((2*n+1)*(2*n+1));       // Same as (2*n+1)^2
        sum += ((2*n+1)*(2*n+1)) - 6*n; // Same as (2*n+1)^2 - 6*n
        sum += ((2*n+1)*(2*n+1)) - 4*n; // Same as (2*n+1)^2 - 4*n
        sum += ((2*n+1)*(2*n+1)) - 2*n; // Same as (2*n+1)^2 - 2*n
    }
 
    printf("Result is: %llu", sum-3);
 
    return 0;
}

I will leave it up to the user to execute the above code to get the result, or to calculate the formulas using some tool.
Hope you enjoyed! :)