euler 27 quadratic primes

Feb 14, 2015  

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
        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
   if max - min < 2
   then if low == elem
        then True
        else False
   else let mid = div (min + max) 2
            midElem = arr V.! mid
         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
   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]]
   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.