Euler Problem 131 – Prime Numbers

Now that I’m on a Haskell kick, I opted to solve this one because of the need for calculating prime numbers. I found tons of resources online that detail different ways to calculate it. I settled on a modified Sieve of Eratosthenes that also takes into account squares, making it faster. Calculating the 78K prime numbers under a million, only takes a few seconds.

The other part of the solution comes from the fact that by playing with the values of the relationship from the problem, we see that n^2 and (n+p) have to be cubes. This makes the prime number a difference of cubes such that prime = (a+1)^3–a^3. This new value stays under a million when a is less than 600. So we just test over this smaller series and count the number of resulting primes. This solution runs in less than 10 secs.

Oh by the way, just for kicks the above image represents the distribution of prime numbers. The source code can be found here.

import Data.List
import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..m])

testEquation :: Integer -> Bool
testEquation a = (((a+1)^3)-(a^3)) `elem` (primes 1000000)

main = print $ length [(((a+1)^3)-(a^3))| a <- [1..600], testEquation a ]