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 - cor­ner­Num­bers + newNumbers.Length pri­meNum­bers - pri­meNum­bers + (newNum­bers |> List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)
if ratio 0.1 && size > 1 then con­tin­ueLoop - false else size - size + 2 size [/code] 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 = this max let max = 100000 // ini­tialise the list with 2 which is the only even num­ber in the sequence let muta­ble pri­meNum­bers = [2] // only check the prime num­bers which are = the square root of the num­ber n let has­Di­vi­sor n = pri­meNum­bers |> Seq.takeWhile (fun n’ -> n’ = int(sqrt(double(n)))) |> Seq.exists (fun n’ -> n % n’ = 0)

// only check odd num­bers = max let poten­tial­Primes = Seq.unfold (fun n -> 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 - pri­meNum­bers @ [n] // use the same has­Di­vi­sor func­tion instead of the prime num­bers list as it offers // far greater cov­er­age as the num­ber n is square root­ed so this func­tion can // pro­vide a valid test up to max*max 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 - cor­ner­Num­bers + newNumbers.Length pri­meNum­bers - pri­meNum­bers + (newNum­bers |> List.filter isPrime |> List.length)

let ratio = double(primeNumbers) / double(cornerNumbers)
if ratio 0.1 && size > 1 then con­tin­ueLoop - false else size - size + 2 size [/code]