Problem 85 asks us to find the number of rectangles that can be drawn in a grid of size m by n.

It may help to work out the answer to a few of the grids until you see the pattern: the number of rectangles is equal to the product of two summations.

(def sums (reductions + (range)))

(defn num-rects [m n] (* (nth sums m) (nth sums n)))

(defn smallest-second [coll]
  (reduce #(if (< (second %1) (second %2)) %1 %2) coll))

(defn euler-85 [goal]
  (first
   (smallest-second
    (for [i (take-while #(< (num-rects % 1) goal) (rest (range)))
          j (take-while #(< 0 (- goal (num-rects i %))) (rest (range)))]
      [(* i j) (- goal (num-rects i j))]))))

(time (euler-85 2000000)) ;; "Elapsed time: 1607.372755 msecs"

Of course the above is straightforward, but we might as well remember the story of Gauss as a young boy and use an analytic solution for num-rects:

(defn num-rects [m n]
  (* (/ (+ (* m m) m) 2)
     (/ (+ (* n n) n) 2)))

(time (euler-85 2000000)) ;; "Elapsed time: 45.927094 msecs"

I’m somewhat surprised that is so much faster – I would have thought that caching the values in the lazy list would have been only slightly slower, but it seems that my intuition was incorrect. The evils of premature optimization appears again.