Project Euler Problem 77

Ivar Thorson bio photo By Ivar Thorson

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.