Project Euler — Problem 28 Solution

Problem

Start­ing with the num­ber 1 and mov­ing to the right in a clock­wise direc­tion a 5 by 5 spi­ral is formed as fol­lows:

image

It can be ver­i­fied that the sum of the num­bers on the diag­o­nals is 101.

What is the sum of the num­bers on the diag­o­nals in a 1001 by 1001 spi­ral formed in the same way?

Solution

let rec sumDiagonals n m total max =
    match n with
    | 1 -> sumDiagonals (n+1) m 1 1
    | _ when n > m -> total
    | _ when n % 2 = 0 -> sumDiagonals (n+1) m total max
    | _ ->
        let newValues = [1..4] |> List.map (fun x -> max + x * (n-1))
        let newMax = newValues |> List.max
        let newTotal = total + (newValues |> List.sum)
        sumDiagonals (n+1) m newTotal newMax

let answer = sumDiagonals 1 1001 0 0

As you’ve prob­a­bly noticed already, there’s a pat­tern in the sequence 1, 3, 5, 7, 9, 13, 17, 21, 25, … gen­er­at­ed by the spi­ral in the prob­lem brief. As the dimen­sion goes up by 2 at a time, all odd num­bers, 4 new num­bers are added to the sequence:

Dimen­sion (d) Num­bers on the edge of the square Max num­ber from last dimen­sion
1 1
3 3, 5, 7, 9 1
5 13, 17, 21, 25 9

Look­ing at the above table, it quick­ly becomes clear that the new num­bers that are added to the diag­o­nals when you expand the dimen­sion by 2 can be cal­cu­lat­ed as:

max num­ber from last dimen­sion + (d-1) * i (where i is a num­ber from 1 to 4)

My solu­tion sim­ply wraps this log­ic in a recur­sive func­tion whilst keep­ing a run­ning total of all the num­bers that have been gen­er­at­ed.