Project Euler Problem 30

Ivar Thorson bio photo By Ivar Thorson

Problem 30 was another very short problem. We just need to find the sum of all numbers that are equal to the sum of the fifth powers of their digits. The only real hard part is to decide at what point we should stop searching. I just arbitrarily picked 1,000,000, and wrote the following.

(use '[clojure.contrib.math :only (expt)])

(defn as-digits [num]
  (map #(Character/getNumericValue %) (str num)))

(defn sum-of-fifth-powers? [num]
  (= num (reduce + (map #(expt % 5) (as-digits num)))))

(defn euler-30 []
  (reduce + (filter sum-of-fifth-powers? (range 10 1000000))))


By sheer luck my original guess of 1,000,000 turned out to be a safe upper search bound, although more conservative than necessary. If you can’t figure out why, see sammay’s explanation on clojure-euler.

Performance of my solution is pretty bad (45 seconds to compute the answer). What can we do to improve speed? Well, we are computing the fifth powers of the numbers 1 to 9 over and over again, which is redundant computation. If we pushed those into map, we could replace an expensive computation with a simple lookup. The other major optimizations would be to stop our search earlier than 1,000,000, and to avoid unnecessary conversion between character and integer types.

Once again, somebody on clojure-euler has beaten us to the punch, and provided this very concise definition that accomplishes all three of these optimizations:

;; Thanks, rafsoaken!
(defn euler-30-rafsoaken []
  (let [pow5 (apply hash-map (interleave (seq "0123456789") 
                                         (map #(Math/pow % 5) (range 10))))
        max  (-> \9 pow5 (* 6))]
    (reduce + (filter #(= % (reduce + (map pow5 (str %)))) 
                      (range 2 max) ))))

This takes less than a second to execute on my machine, easily 50 times faster than my first solution.