Project Euler — Problem 58 Solution

Problem

Start­ing with 1 and spi­ralling anti­clock­wise in the fol­low­ing way, a square spi­ral with side length 7 is formed.

image

It is inter­est­ing to note that the odd squares lie along the bot­tom right diag­o­nal, but what is more inter­est­ing is that 8 out of the 13 num­bers lying along both diag­o­nals are prime; that is, a ratio of 8/13 ? 62%.

If one com­plete new lay­er is wrapped around the spi­ral above, a square spi­ral with side length 9 will be formed. If this process is con­tin­ued, what is the side length of the square spi­ral for which the ratio of primes along both diag­o­nals first falls below 10%?

Solution

let hasDivisor(n) =
let upper­Bound = 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 func­tion that returns the num­ber on the cor­ners of a spi­ral of length n
let get­Corner­Num­bers 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 muta­ble cor­ner­Num­bers, pri­meNum­bers, size = 0, 0, 1
let muta­ble con­tin­ueLoop = true

while con­tin­ueLoop do
// get the num­bers that appear at the cor­ners of a spi­ral of the giv­en size
let newNum­bers = get­Corner­Num­bers size

// incre­ment the totals
cor­ner­Num­bers List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)
if ratio 1 then con­tin­ueLoop UPDATE: Hav­ing stum­bled upon some very good algo­rithms for gen­er­at­ing prime num­ber sequence here, I decid­ed to revis­it my solu­tion here and using the PGSimple3 algo­rithm the new code now runs in sec­onds!

// gen­er­ate all prime num­bers under Seq.takeWhile (fun n’ -> n’ Seq.exists (fun n’ -> n % n’ = 0)

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

// pop­u­late the prime num­bers list
for n in poten­tial­Primes do
if not(hasDivisor n) then pri­meNum­bers [1]
| _ when n % 2 = 0 -> []
| _ -> [3..-1..0] |> List.map (fun n’ -> n*n — n’*(n-1))

let answer =
let muta­ble cor­ner­Num­bers, pri­meNum­bers, size = 0, 0, 1
let muta­ble con­tin­ueLoop = true

while con­tin­ueLoop do
// get the num­bers that appear at the cor­ners of a spi­ral of the giv­en size
let newNum­bers = get­Corner­Num­bers size

// incre­ment the totals
cor­ner­Num­bers List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)
if ratio 1 then con­tin­ueLoop