# Euler Solution 87

### From ProgSoc Wiki

# 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.

## Haskell by SanguineV

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 = {} # Add, add, add 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)