Project Euler Problem 53

Ivar Thorson bio photo By Ivar Thorson

Problem 53 asks us a very basic fact about the number of combinations that can be generated when starting with n objects and removing r of them.

With the large bag of tricks collected up until now, problems like this become a snap to solve. As with problem 15, we can greatly improve performance by caching values of various factorials in a lazy sequence factorials.

(def factorials (map #(reduce * (range 1 (inc %))) (range)))

(defn fact [n] (nth factorials n))

(defn n-choose-r [n r] (/ (fact n) (* (fact r) (fact (- n r)))))

(defn euler-53 []
   (for [n (range 1 101)
         r (range 1 n)
         f [(n-choose-r n r)]
         :when (> f 1000000)]

(time (euler-53)) ;; "Elapsed time: 56.529224 msecs"

Coffee time!