Problem 78 is the third and final of the integer partitioning problems, but because of the rather large number of possibilities it was rather more difficult.

The first attempt started quite similarly to the previous two problems:

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

(defn integer-partitions [n]
  (inc (integer-tree (reverse (range 1 n)) n)))

(defn euler-78 []
  (first
   (for [n (iterate inc 2)
         :when (zero? (mod (integer-partitions n) 1000000))]
     n)))

(time (euler-78)) ;; Blows stack

Stack overflows, oh my! Let’s try that again, using a similar but slightly different algorithm:

;; Using algorithm from : http://en.wikipedia.org/wiki/Integer_partition
(def pp (memoize
         (fn [k n]
           (cond
            (> k n) 0
            (= k n) 1
            :else (+ (pp (inc k) n)
                     (pp k (- n k)))))))

(defn euler-78-b [x]
  (first (drop-while #(not (zero? (mod (second %) x)))
                     (map (fn [n] [n (pp 1 n)]) (iterate inc 1)))))

(euler-78-b 10000) ;; Blows the stack above 10000

Well, that didn’t work either!

A little bit of hunting around and I found the property that the Project Euler people must have wanted us to exploit: that pentagonal numbers are closely related to the Euler function by the Pentagonal Number Theorem. Unfortunately, wikipedia is a little vague about how to use generalized pentagonal numbers to generate integer partitions, but a little effort with google and you should be able to find some more details into the underlying mathematics.

;; Using the pentangonal number theorem
;; http://en.wikipedia.org/wiki/Pentagonal_number_theorem

;; Use the recurrence relationship using generalized pentagonal numbers
;; p(k) = + p(k − 1) + p(k − 2)
;;        − p(k − 5) − p(k − 7)
;;        + p(k − 12) + p(k − 15)
;;        − p(k − 22) − ... 

(defn pentagonal [n] (/ (* n (- (* 3 n) 1)) 2))

(def generalized-pentagonals
     (map pentagonal (cons 0 (interleave (iterate inc 1)
                                         (iterate dec -1)))))

(def num-partitions
     (memoize
      (fn [k]
        (if (<= k 1)
          1
          (let [pent (take-while #(<= % k) (rest generalized-pentagonals))
                sign (cycle [1 1 -1 -1])]
            (reduce + (map (fn [s p] (* s (num-partitions (- k p))))
                           sign
                           pent)))))))

(defn euler-78-c [x]
  (first (drop-while #(not (zero? (mod (second %) x)))
                     (map (fn [n] [n (num-partitions n)]) (iterate inc 1)))))

(time (euler-78-c 1000000)) ;; "Elapsed time: 8746.114811 msecs"

Aha! There we go.