Problem 77 tests our ability to write correct, reusable code because problems 76, 77, and 78 all use roughly the same algorithm and ask for integer partitions of a particular number. This time, the partitioning must be done using only prime numbers.

Unfortunately, I’m going to have to admit I haven’t properly abstracted the algorithm that should solve and 76, 77, 78. I needed to twiddle with the details of the central function to get it to work properly. In this problem, total-sums is nearly identical to integer-sums-memo in the previous problem, with a couple very small tweaks that really should be ignorable.

(use '[clojure.contrib.lazy-seqs :only (primes)])

(defn gcd [a b] (if (zero? b) a (recur b (mod a b)))) 

(def total-sums
     (memoize
      (fn [c v]
        (let [f (first c)]
          (cond
           (nil? f) 0
           (and (= f (last c))
                (zero? (mod v f))) 1
           :else (reduce + (for [n (range 0 (inc (quot v f)))]
                             (total-sums (rest c) (- v (* n f))))))))))

(defn num-prime-sums [n]
  (total-sums (reverse (take-while #(< % n) primes)) n))

(defn euler-77 []
  (first
   (for [n (iterate inc 1)
         :when (< 5000 (num-prime-sums n))]
     n)))

(euler-77) ;; "Elapsed time: 60.048583 msecs"

If you find a better way properly generalize these solutions, please let me know…I don’t quite have this one.