Problem 28 of Project Euler reads
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?
I am pretty sure it is possible to brute force a solution for this problem, but the thought of having to construct the spiral, so let instead of that let us attack it from a more analytical approach and search for a function of the ring number. This is done in two steps, first we will derive a formula where the calculation for the n’th ring depends on the n-1’th ring. And after that we will derive a formula which is independent on the previous ring.
Deriving the formula for the corners of the ring
Lets start with the definitions as any good mathematician would do.
n is the ring number, starting from 0. Such that n=1 is the ring
7 8 9 6 2 5 4 3
and so on.
f(n) is the sum of diagonals for the the rings up to and including n.
We will need to find the corner values in the ring, and since n=0 is not a ring but a point I will treat it as a special case. Such that f(0) = 1.
The sides of a ring is 2n+1 wide, and thus the upper right corner in the ring is (2n+1)2, since it is equal to the area of the square.
Moving counter clockwise, in order to get to the second corner, we will take the value of the first corner and deduct the side length minus 1 from. since both numbers are included in the side. Such that the formula for the second corner is (2n+1)2 – 2n.
In order to get the third corner we once again deduct 2n, and the same thing for the fourth corner.
Summing all the corners we get
4(2n+1)2 – 12n
That means the sum of the diagonals can be written as
f(n) = 4(2n+1)2 – 12n + f(n-1)
Now it should be pretty easy to make a for loop for calculating f(500). However, I want to take a bit further.
Deriving a non-iterative formula
Since we are working with a fairly nice formula, there is good chance that we can fit a polynomial to get an analytical solution for f(n). We used the same trick in the solution for problem 6 though we never proved it. The method uses differences and can also be seen at Ken Ward’s Mathematics Pages.
In order to figure out what order polynomial we need, we need to calculate the function value of f(n) and we need to calculate the differences. Δ1(n) represents the differences between f(n) and f(n-1). Δ2(n) = Δ1(n) – Δ1(n-1). and so on
Since a the third difference gives us a constant, we will need a third order polynomial function in order to fit f(n). We want to find the factors for the function
f(n) = ax3 + bx2 + cx + d
That means a total of 4 unknown factors, which can be found if we solve four equations. So lets solve the equations related to f(0) – f(3).
d = 1
a + b+ c + d = 25
8a + 4b + 2c + d = 101
27a + 9b + 3c + d = 261
This can be solved in a multitude of ways. My preferred way would be to state it as a linear algebra problem, but we could also solve it by isolating and inserting into the equations.
I have the videos from a course taught by Gilbert Strang on Linear algebra, from which you will need the first two lectures in order to be able to solve this set of linear equations. I wont show you how to solve the set of equations here, but recommend you the videos. Along with that I will recommend you two books. The one I used in university Linear Algebra and Its Applications by David C. Lay and the other is by Gilbert Strang Introduction to Linear Algebra.
Many modern calculators like TI 83 is fully capable of calculating the unknowns for you. However, I will strongly recommend you to do it by hand until you master it. Only then should you do it on a calculator or a program. It sounds old and harsh to say that, but over and over again, I keep realising that I understand the math building on top of the fundamentals only when I master the fundamentals.
After my little trip on the soap box, the result of solving the four equations is that the function
f(n) = 16/3x3 + 10x2 + 26/3x + 1
So now we have a complete analytical solution to any size spiral. The solution to the specific question is
f(500) =16/3*5003 + 10*5002 + 26/3*500 + 1 = 669 171 001
No computer code this time, just one single formula.