Project Euler problem 12 was the hardest so far, despite it’s simplicity. I started of course with a brute force approach, since it is quick to write:

(def triangle-nums (map first (iterate (fn [[n m]] [(+ n m) (+ m 1)]) [1 2])))

(defn num-divisors-slow [n]
  (+ 1 (count (filter zero? (map #(mod n %) (range 1 (+ 1 (/ n 2))))))))

(defn euler-12-slow [divisors]
  (first (drop-while #(> divisors (num-divisors-slow %)) triangle-nums)))

But when I saw how terrible the performance of such an algorithm was, I realized I would need to become more clever about how I found the number of divisors. My intuition told me that it must involve prime factors, so I wrote a function in the style of in problem 3 to return a list of all prime factors in the correct multiplicity:

(defn prime-factors-of [num]
  "Returns a sorted list of prime factors of num, including multiplicity."
  (let [q (Math/sqrt num)
        factor? (fn [nom den] (zero? (rem nom den)))] 
    (loop [n num
           d 2
           r []]
      (cond
       (> d q) (concat r [n]) 
       (= n d) (concat r [n])      
       (factor? n d) (recur (/ n d) d (conj r d)) 
       true          (recur n (inc d) r)))))

Great, huh? I was happy with how easily that particular insight had come…clearly thinking about prime numbers so much in problem 7 organized something in my mind.

But then I got completely stuck, for probably 2-3 hours, as I tried to work out by hand the rule for computing the number of proper divisors of a number based on its prime factors. It didn’t seem like a simple combination or permutation…maybe it had something to do with binomials? Chaos ruled my mind, and I got stuck thinking of ways to generate every possible divisor

When I regained my senses, I embarrassedly looked around on the appropriate page of wikipedia. The number of proper divisors is simply (a+1)(b+1)(c+1)... , where a,b,c are the multiplicity of each factor. For example, the number 12 has the prime factors (2,2,3). The multiplicity of 2 is 2, and the multiplicity of 3 is 1. So the number of divisors is (2+1)(1+1)=6, which is indeed true (1,2,3,4,6,12).

Much simpler than I had thought! At this point, the solution wrote itself:

(defn num-divisors-fast [num]
  (let [freqs (reduce #(assoc %1 %2 (inc (get %1 %2 0)))
                      {} (prime-factors-of num))]
    (reduce #(* %1 (inc %2)) 1 (vals freqs))))

(defn euler-12-fast [divisors]
  (first (drop-while #(> divisors (num-divisors-fast %)) triangle-nums)))

(euler-12-fast 500)

Ahh, beautiful!