Thought I’d post up my solution to Problem 28 on Project Euler.
After the answer was submitted I read through some of the other code the people have posted. It seems that there are a lot more programmers than mathematicians because almost all of the solutions were brute-force algorithms… and quite a few were written in assembly. *shrug*
Anyway, here is the problem.
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 13It can be verified that the sum of both diagonals is 101.
What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?
The first you to notice is that you don’t have to actually construct the spiral in order to solve this problem. It can be shown quite simply that in an nxn spiral, the values of the four corners are as follows:
top-right: n^2
top-left: n^2 - n + 1
bottom-left: n^2 - 2n + 2
bottom-right: n^2 - 3n + 3
Adding all that up yields 4n^2 -6n + 6.
At this point you can easily loop through from 3 to 1001 (in increments of 2) and add up the results. Just make sure you add a 1 to the results for the base case. :)
Of course, if you’re like me you wouldn’t be satisfied with that result. All we’re dealing with are some simple summations, so the result for an nxn spiral should be easily expressed by a formula. In fact, here’s the formula.
Sum(i = 1:500)[4(2*i + 1)^2 - 6(2i + 1) +6]
The beginning reads “sum from i=1 to 500″… I’m not too sure how to type out sigma notations properly.
Converting the summation into closed form gives the formula we’re looking for. I’m leaving out the steps, but it’s fairly simple anyway.
(16n^3)/3 + (10n^2)/2 + 26n/3
And here is the complete solution in Python.
from math import pow
def prob28(n): return (16*pow(n, 3) + 26*n)/3 + 10*pow(n, 2)
print prob28(500) + 1
January 11th, 2009 at 3:52 am
Really Cool !
May 26th, 2011 at 1:06 pm
How did you figure out those formulas? Just by looking at it or is this a common thing?
May 26th, 2011 at 1:07 pm
How did you figure out those formulas? Just by looking at it or is this a common pattern?
August 7th, 2011 at 1:28 am
Here is the explaination provided by Colin Hughes on the forum for the problem.
Like many problems here they can be solved analytically, and this always adds another layer to the problem for the committed.
In my post above I showed that the sum of four corners for an nxn grid is given by 4n2-6n+6.
So we need to add that expression from n=3 to n=1001 in steps of 2.
The sum of the first k odd squares is k(4k2-1)/3.
The sum of the first k odd numbers is k2.
So we get S=4k(4k2-1)/3-6k2+6k.
Substituting in k=501 (1001 is the 501st odd), we get S=669171004, but this sum includes for when n=1. As the expression gives 4 for this, we need to subtract 4 and add 1 (the value at the centre), giving 66917003.