I found this one to be rather interesting, but maybe I just had a lot of coffee this morning and am in an especially good mood. Problem 39 asks us to find the number n < 1000 for which there are the most number of right triangles with integer sides and a perimeter of n.

Although we could generate triangles at random and then check that they are right triangles using a brute force approach, why would we do that when a variety of equations already let us generate the so-called “pythagorean triples” directly?

(defn pythagorean-triple [m n k]
  "Uses Eulcid's formula to generate pythagorean triples."
  (map #(* k %) [(- (* m m) (* n n)) (* 2 m n) (+ (* m m) (* n n))]))

(defn pythagorean-perimeters [p]
  (let [sq (int (Math/sqrt p))]
    (into #{}
          (for [n (range 1 sq)
                m (range (inc n) sq)
                k (range 1 (/ p (+ (* m m) (* n n))))
                t [(sort (pythagorean-triple m n k))]
                :when (>= p (apply + t))]
            t))))

(defn euler-39 []
  (let [h (reduce (fn [hsh e]
                    (if (nil? (hsh e))
                      (assoc hsh e 1)
                      (assoc hsh e (inc (hsh e)))))
                  {}
                  (map #(apply + %) (pythagorean-perimeters 1000)))]
    (reduce #(if (> (h %1) (h %2)) %1 %2) (keys h))))

(time (euler-39)) ;; "Elapsed time: 33.017842 msecs"

Writing pythagorean-perimeters was a little tricky, but once that was in place, pushing everything into a hashmap was a simple way to record the number of ways a particular perimeter could be formed. Performance seems very good, although I think euler-39 could still be improved somehow by using a standard sequence function…

(defn euler-39 []
  (let [h (frequencies (map #(apply + %) (pythagorean-perimeters 1000)))]
    (reduce #(if (> (h %1) (h %2)) %1 %2) (keys h))))

Ahh, that’s much better.