problem012.clj

;; The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

;; 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

;; Let us list the factors of the first seven triangle numbers:

;;  1: 1
;;  3: 1,3
;;  6: 1,2,3,6
;; 10: 1,2,5,10
;; 15: 1,3,5,15
;; 21: 1,3,7,21
;; 28: 1,2,4,7,14,28
;; We can see that 28 is the first triangle number to have over five divisors.

;; What is the value of the first triangle number to have over five hundred divisors?

(def triangles (cons 0 (lazy-seq (map + triangles (iterate inc 1)))))

(use 'clojure.contrib.math)
(defn count-divisors [n]
  "Counts the number of unique divisors for the provided number"
  ;; for every divisor < the square root of n, there exists a divisor
  ;; > the square root of n. This means we only need to find the
  ;; divisors smaller then (sqrt n) and then multiply by 2.
  ;; One edge case is where n is a perfect square, in which case we
  ;; need to add 1.
  (let [root (sqrt n)
        divs (* 2 (count (filter #(zero? (rem n %)) (range 1 root))))]
    (if (= (* root root) n)
      (inc divs)
      divs)))

(defn euler-12 [n]
  "Return the first triangle number to have n divisors"
  (first (filter #(>= (count-divisors %) n) triangles)))

(euler-12 501)