Project Euler Problem 87

Ivar Thorson bio photo By Ivar Thorson

Problem 87 asks us to find how many numbers below 50 million that can be expressed as the sum of a prime square, cube, and fourth power.

By now we are old hands at this type of problem. By caching the exponents of prime numbers and using a set to filter out duplicates, we can find the solution in roughly 4 seconds:

(defn euler-87 [top]
    (let [squares (map #(expt % 2) primes)
          cubes   (map #(expt % 3) primes)
          quads   (map #(expt % 4) primes)]
      (for [i (take-while #(< % top) squares)
            j (take-while #(< % (- top i)) cubes)
            k (take-while #(< % (- top i j)) quads)
            s [(+ i j k)]
            :when (< s top)]

(time (euler-87 50000000))  ;; "Elapsed time: 3954.751452 msecs"