Project Euler Problem 75

Ivar Thorson bio photo By Ivar Thorson

Once again, to solve Problem 75 our first stop should be Wikipedia’s page on Pythagorean Triples.

It may be interesting for you to consider how this compares with the code from Problem 39. You may note that this problem slightly improves the performance and correctness of the method that generates Pythagorean Triples.

(use '[clojure.contrib.math :only (abs)])

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))

(defn coprime? [p q] (= 1 (gcd p q)))

;; Modification of Problem 39's function
(defn pythagorean-perimeters
  "Returns frequencies of all pythagorean triple perimeters less than L."
  (->> (for [sq [(int (Math/sqrt L))]
             n (range 1 sq 2)
             m (range 2 sq 2)
             :when (coprime? m n)       ;; Avoid duplicates
             p [(+ (abs (- (* m m) (* n n)))
                   (* 2 m n) (* m m) (* n n))]
             k (range 1 (/ (inc L) p))] ;; scaled triangles also give perims
         (* p k))

(defn euler-75 [n]
  (count (filter #(= 1 (second %)) (pythagorean-perimeters n))))

(time (euler-75 1500000)) ;; "Elapsed time: 16164.056504 msecs"

That’s enough for today!