#### Problem

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

#### Solution

let hasDivisor(n) =

let upperBound = int(sqrt(double(n)))

[2..upperBound] |> Seq.exists (fun x -> n % x = 0)

let isPrime(n) = if n = 1 then false else not(hasDivisor(n))

// define function that returns the number on the corners of a spiral of length n

let getCornerNumbers n =

match n with

| 1 -> [1]

| _ when n % 2 = 0 -> []

| _ -> [3..-1..0] |> List.map (fun n’ -> n*n — n’*(n-1))

let answer =

let mutable cornerNumbers, primeNumbers, size = 0, 0, 1

let mutable continueLoop = true

while continueLoop do

// get the numbers that appear at the corners of a spiral of the given size

let newNumbers = getCornerNumbers size

// increment the totals

cornerNumbers List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)

if ratio 1 then continueLoop UPDATE: Having stumbled upon some very good algorithms for generating prime number sequence here, I decided to revisit my solution here and using the *PGSimple3* algorithm the new code now runs in seconds!

// generate all prime numbers under Seq.takeWhile (fun n’ -> n’ Seq.exists (fun n’ -> n % n’ = 0)

// only check odd numbers if n > max then None else Some(n, n+2)) 3

// populate the prime numbers list

for n in potentialPrimes do

if not(hasDivisor n) then primeNumbers [1]

| _ when n % 2 = 0 -> []

| _ -> [3..-1..0] |> List.map (fun n’ -> n*n — n’*(n-1))

let answer =

let mutable cornerNumbers, primeNumbers, size = 0, 0, 1

let mutable continueLoop = true

while continueLoop do

// get the numbers that appear at the corners of a spiral of the given size

let newNumbers = getCornerNumbers size

// increment the totals

cornerNumbers List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)

if ratio 1 then continueLoop