Often the hardest part about Project Euler is to discover what page of wikipedia to read for the mathematical theory behind the problem. In the case of problem 76, we need to do some reading on Integer Partitions.

;; A renamed function from Problem 31
(defn integer-sums [c v]
  (let [f (first c)]
    (if (= f 1) 1
      (reduce + (for [n (range 0 (inc (quot v f)))]
                  (integer-sums (rest c) (- v (* n f))))))))

(defn euler-76 []
  (integer-sums (reverse (range 1 100)) 100))

(time (euler-76)) ;;   "Elapsed time: 478118.487234 msecs"

Then I thought…wait a second, I’m repeating a hell of a lot of computation there in this recursive formulation! Let’s memoize this sucker:

(def integer-sums-memo
     (memoize
      (fn [c v]
        (let [f (first c)]
          (if (= f 1) 1
              (reduce + (for [n (range 0 (inc (quot v f)))]
                          (integer-sums-memo (rest c) (- v (* n f))))))))))

(defn euler-76-memo []
  (integer-sums-memo (reverse (range 1 100)) 100))

(euler-76-memo) ;; "Elapsed time: 89.610866 msecs"

I love how versatile memoization is as a way of caching or representing a data structure that is being described by a function. The 400,000x speedup isn’t bad, either.