# Euler Solution 87

(Difference between revisions)
 Revision as of 09:29, 21 May 2009 (view source)← Older edit Latest revision as of 01:31, 22 July 2011 (view source)Althalus (Talk | contribs) (→Solutions for Problem 87) Line 43: Line 43: {- Return the length of all the numbers -} {- Return the length of all the numbers -} main = print (length (toLim 50000000 p2 p3 p4)) 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) [[Category: Euler]] [[Category: Euler]]

# 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)
```