Project Euler Problem #28:

Problem #28 is the type of counting problem that is very annoying to do legitimately. The question reads:

Project Euler Problem 28: 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?

As stated above, I find this problem to be very annoying. As a result, I decided to use one of my favorite strategies for solving problems involving complex patterns such as this. Here’s my solution:

Solution #1: Engineer’s Induction Approach

For those who don’t know, one of the most common techniques for writing mathematical proofs is mathematical induction. When proving a claim for all positive integers n, induction is the technique of proving the claim is true when n = 1, assuming it is true when n = x, and using that assumption to prove the claim is true when n = x+1. The technique is often compared to dominoes falling over each other representing each integer proving the claim for the next integer.

Engineer’s induction, on the other hand, is a far more practical technique involving patterns. The technique involves finding a pattern, observing it to be true for the first few terms, and then assuming it will be true forever. This technique can be used to trivialize incredibly complex problems such as Problem #27.

My observation was that looking strictly at the numbers above and to the right of 1 in the 5×5 spiral, we see the numbers 1, 9, and 25 in order. 9 – 1 = 8, and 25 – 9 = 16. 16 – 8 = 8. Doing the same for numbers below and to the right of 1, we see the numbers 1, 3, and 13. 3 – 1 = 2, and 13 – 3 = 10. 10 – 2 = 8. Continuing with the numbers below and to the left of 1, we see the numbers 1, 5, and 17. 5 – 1 = 4, and 17 – 5 = 12. 12 – 4 = 8. Finally, with the numbers above and to the left of 1, we see the numbers 1, 7, and 21. 7 – 1 = 6, and 21 – 7 = 14. 14 – 6 = 8. Based on these observations, I used Engineer’s Induction to find that the increase between each corner and the next corresponding corner would increase by 8 between each concentric ring centered around the 1 in the spiral. For example, 3 – 1 = 2, 13 – 3 = 10. I would expect the next difference to be 10 + 8 = 18 and therefore the next bottom left corner to be 13 + 18 = 31. We can quickly check that this is true. Assuming this pattern is true forever, we can use these observations to get a solution. Here is a solution that uses these observations that is written in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Engineer's Induction Approach to Project Euler Problem #28
 '''

 import time

 def projectEulerProblemTwentyEight(n):
     total = 1
     layers = (n+1)/2
     last = 4
     for i in range(1,layers):
         last = last + (32*i-12)
         total+=last
     return total

 start = time.time()
 print projectEulerProblemTwentyEight(1001)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 669171001
 --- 4.72068786621e-05 seconds ---

 for input of n = 1001
 '''

Entering this answer into Project Euler, we see that it is correct. Therefore, Engineer’s Induction solved the problem for us. Translation: I’m too lazy to actually solve this problem. It makes sense that the second finite differences between each ring should be constant as the top right corner of each (2n+1) x (2n+1) concentric ring is a new square number. Without being rigorous, this observation suggests that the pattern we found will continue.

Hopefully I didn’t annoy you too much by not providing a legitimate solution to this problem. Thanks for reading!