Statutory Warning: Spoilers ahead
This turned out to be really simple, though I went through a phase of churning out complicated solutions because of a stupid mistake.
I didn’t preserve intermediate versions, so here is the final solution:
import qualified Data.List as L import qualified Data.Vector as V import qualified Data.Function as F sieve :: Int -> [Int] -> [Int] sieve num list = if null list then [num] else let rest = filter (\x -> x `mod` num > 0) list in num : sieve (head rest) (tail rest) eratosthenes :: Int -> [Int] eratosthenes maxNum = sieve 2 [3 .. maxNum] allPrimes :: Int -> V.Vector Int allPrimes maxNum = V.fromList $ eratosthenes maxNum eulerEqn :: Int -> Int -> Int -> Int eulerEqn a b n = n * n + a * n + b -- TODO(agam): replace with the "standard" way to do binary search binSearch :: V.Vector Int -> Int -> Int -> Int -> Bool binSearch arr min max elem = let low = arr V.! min high = arr V.! max in if max - min < 2 then if low == elem then True else False else let mid = div (min + max) 2 midElem = arr V.! mid in if midElem > elem then binSearch arr min mid elem else binSearch arr mid max elem consecutivePrimes a b primes start length = let p = eulerEqn a b start l = V.length primes isPrime = binSearch primes 0 l p in if isPrime then consecutivePrimes a b primes (start + 1) (length + 1) else length numPrimes a b primes = consecutivePrimes a b primes 0 0 euler27 maxNum = let ap = allPrimes maxNum primeLengths = [(a * b, numPrimes a b ap) | a <- [-1000 .. 1000], b <- [-1000 .. 1000]] in L.maximumBy (F.on compare snd) primeLengths
When I ran this (i.e.
euler27 1000) I got the correct answer the first time! But I didn’t see it. Instead, I entered the second value of the tuple, which is not the one asked for, and it was therefore obviously wrong. So I thought “hmm, we’re looking at some large repeating sequence among really large primes”, and tried
euler27 100000 and
euler27 10000000, with no luck.
The last one kept running for hours and I killed it, and then came up with the idea of “vectorizing everything” – which was perhaps a good academic exercise but did absolutely nothing for the performance here.
So I forgot about it for a while, then came back and ran
euler27 1000, entered the first value of the tuple, and that was the end of this story.