Project Euler Problem 28 Solution

Question

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?

Haskell

main :: IO ()
main = print $ foldr (+) 1 [4*n^2 - 6*n + 6 | n <- [3,5..1001]]
$ ghc -O2 -o spiral spiral.hs
$ time ./spiral
real   0m0.001s
user   0m0.000s
sys    0m0.000s

Python

#!/usr/bin/env python
def sum_diagonals_of_spiral(size):
    n = 1
    step = 2
    total = 0
    since_last = 0
    while n <= size**2:
        total += n
        n += step
        since_last += 1
        if since_last == 4:
            step += 2
            since_last = 0
    return total

print(sum_diagonals_of_spiral(1001))
$ time python3 spiral.py
real   0m0.035s
user   0m0.024s
sys    0m0.008s

Ruby

#!/usr/bin/env ruby
i = 1
sum = i
step = 2
until i >= 1001**2
  4.times { sum += i += step }
  step += 2
end
puts sum
$ time ruby spiral.rb
real   0m0.036s
user   0m0.028s
sys    0m0.004s

Questions? Comments? Send me an email: z@chdenton.com