Feb 14, 2015

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.