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.