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.002s
user   0m0.002s
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.017s
user   0m0.017s
sys    0m0.000s

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.039s
user   0m0.023s
sys    0m0.016s

Rust

fn main() {
    let sum = (1..501)
        .map(|i| {
            let n = 2 * i + 1;
            4 * n * n - 6 * n + 6
        })
        .sum::<u64>() + 1;
    println!("{}", sum);
}

$ rustc -C target-cpu=native -C opt-level=3 -o spiral spiral.rs
$ time ./spiral
real   0m0.001s
user   0m0.000s
sys    0m0.001s