Hi all,
I've been trying to work my way through Problem 27 of Project Euler, but this one seems to be stumping me. Firstly, the code is taking far too long to run (a couple of minutes maybe, on my machine, but more importantly, it's returning the wrong answer though I really can't spot anything wrong with the algorithm after looking through it for a while.
Here is my current code for the solution.
/// Checks number for primality.
let is_prime n =
[|1 .. 2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)
/// Memoizes a function.
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
let found, res = cache.TryGetValue(x)
if found then
res
else
let res = f x
cache.[x] <- res
res
/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
let is_prime_mem = memoize is_prime
let range = [|-(n - 1) .. n - 1|]
let natural_nums = Seq.init_infinite (fun i -> i)
range |> Array.map (fun a -> (range |> Array.map (fun b ->
let formula n = n * n + a * n + b
let num_conseq_primes = natural_nums |> Seq.map (fun n -> (n, formula n))
|> Seq.find (fun (n, f) -> not (is_prime_mem f)) |> fst
(a * b, num_conseq_primes)) |> Array.max_by snd)) |> Array.max_by snd |> fst
printn_any (problem27 1000)
Any tips on how to a) get this algorithm actually returning the right answer (I think I'm at least taking a workable approach) and b) improve the performance, as it clearly exceeds the "one minute rule" set out in the Project Euler FAQ. I'm a bit of a newbie to functional programming, so any advice on how I might consider the problem with a more functional solution in mind would also be appreciated.