# Solutions for Problem 87

Find the number of numbers below 50 million that can be written as the sum of a prime squared, a prime cubed and a prime to the four.

Runtime: 72 seconds

{- Primes as usual -}
primes :: [Integer]
primes = 2:3:primes'
where
1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
primes'         = p : filter isPrime candidates
isPrime n       = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes'
divides n p     = mod n p == 0

{- Predefine the primes squared, cubed, etc. -}
p2 = map (\x -> x * x) primes
p3 = map (\x -> x * x * x) primes
p4 = map (\x -> x * x * x * x) primes

{- Merge two sorted lists of integers removing duplicates -}
merge :: [Integer] -> [Integer] -> [Integer]
merge [] bbs = bbs
merge aas [] = aas
merge aas@(a:as) bbs@(b:bs) =
case compare a b of
LT -> a : merge as bbs
EQ -> a : merge as bs
GT -> b : merge aas bs

{- Return all the numbers that can be expressed as a prime squared + prime
- cubed + a prime t the four. -}
toLim :: Integer -> [Integer] -> [Integer] -> [Integer] -> [Integer]
toLim lim (a:as) (b:bs) (c:cs) | a + b + c >= lim = []
toLim lim (a:as) bbs ccs = merge (inner (map (\x -> a + x) bbs) ccs) (toLim lim as bbs ccs)
where
inner :: [Integer] -> [Integer] -> [Integer]
inner (b:bs) (c:cs) | b + c >= lim = []
inner (b:bs) cs = merge (takeWhile (< lim) (map (\x -> x + b) cs)) (inner bs cs)

{- Return the length of all the numbers -}
main = print (length (toLim 50000000 p2 p3 p4))

## Python by Althalus

Time: 2.5 seconds

from primeFunctions import genPrimes

# Always with the primes
primes = genPrimes(7072)
# prime squares
primes2 = map(lambda x: x**2, primes)
# prime cubes
primes3 = map(lambda x: x**3, primes)
# prime to the four
primes4 = map(lambda x: x**4, primes)
results = {}

for x in primes2:
for y in primes3:
if x+y > 50000000:
break
for z in primes4:
res = x+y+z
if res > 50000000:
break
results[res] = 1

print len(results)