Claudio Cherubino's blog Life of a Googler

Project Euler in F# – Problem 28

Sometimes, when I find a problem like Project Euler problem 28, I remember that human beings are smarter than computers.

Let's read the problem statement, it doesn't seem easy at first glance:

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 both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

If we don't think of anything creative, we are forced to write an algorithm to draw that 1001x1001 number spiral and then sum both diagonals together.

However, we can start noticing that the number in the top-right position is always n^2, where n is the length of one side of the spiral. In the example, the spiral is 5 by 5 and the top-right value is 25. In a 3 by 3 spiral it would be 9, 49 in a 7 by 7 spiral and so on.

If we concentrate on the outer ring of the spiral, then the inner sum can be obtained by recursion, so we only need to find a trick for the top-left, bottom-left and bottom-right numbers.

They are 21, 17 and 13 in a 5x5 spiral, so it seems like they can be computed starting from the top-right number and repeatedly subtracting 4 (i.e. n - 1).

Let's check this theory with the 3x3 spiral: the top-right number is 9, the other corners are 7, 5 and 3. We are indeed subtracting 2 (i.e. n - 1) each time!

Let's summarize: given a n x n spiral we have to sum n^2, n^2 - (n-1), n^2 - 2(n-1) and n^2 - 3(n-1).

Some elementary math and we get 4n^2 - 6n + 6 for each ring of the spiral.
The base case of the recursion is the 1x1 spiral and in that case the (degenerate) diagonal sum is 1.

Given these premises it is very easy to write the F# code to implement the algorithm:

let rec euler28 n =
  match n with
  | 1 -> 1
  | _ -> euler28 (n-2) + (4 * n * n) - (6 * n) + 6

An improvement of the code above would be using tail recursion, which means that the last operation of the function should be a recursive call. This leads to a reduction of the stack space used from O(n) to O(1) and let us avoid stack overflow exceptions:

let tail_euler28 n =
  let rec spiral n sum =
    match n with
    | 1 -> sum + 1
    | _ -> spiral (n - 2) (sum + (4 * n * n) - (6 * n) + 6)
  spiral n 0

As it is usually done in tail recursion, we define an accumulator parameter (sum in the example) which is used to store the partial result of the computation, eliminating the need to keep the state on the stack.

In both solutions I've left a bug that can lead to an infinite loop. Can you spot it?

#light
open Microsoft.FSharp.Math.BigInt

// Greater Common Divisor
let rec gcd a b =
 match b with
 | b when b = 0I -> a
 | b -> gcd b (a % b)

// Least Common Multiple
let lcm a b = a * b / (gcd a b)

let answer = Seq.fold1 lcm [1I .. 20I]