Pythagorean triples: Difference between revisions

=={{header|Clojure}}==

This version is based on Euclid's formula:

for each pair ''(m,n)'' such that ''m>n>0", ''m'' and ''n'' cop rime and of opposite polarity (even/odd),

there is a primitive Pythagorean triple. It can be proven that the converse is true as well.

<lang clojure>(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))

(defn pyth [peri]

(for [m (range 2 (Math/sqrt (/ peri 2)))

n (range (inc (mod m 2)) m 2) ; n<m, opposite polarity

:let [p (* 2 m (+ m n))] ; = a+b+c for this (m,n)

:while (<= p peri)

:when (= 1 (gcd m n))

:let [m2 (* m m), n2 (* n n),

[a b] (sort [(- m2 n2) (* 2 m n)]), c (+ m2 n2)]

k (range 1 (/ (inc peri) p))]

[(= k 1) (* k a) (* k b) (* k c)]))

(defn rcount [ts]

(reduce (fn [[total prims] t] [(inc total), (if (first t) (inc prims) prims)])

[0 0]

ts))</lang>

To handle really large counts, we can dispense with actually generating the triples and just do the counts:

<lang clojure>(defn pyth-count [peri]

(reduce (fn [[total prims] k] [(+ total k), (inc prims)]) [0 0]

(for [m (range 2 (Math/sqrt (/ peri 2)))

n (range (inc (mod m 2)) m 2) ; n<m, opposite polarity

:let [p (* 2 m (+ m n))] ; = a+b+c for this (m,n)

:while (<= p peri)

:when (= 1 (gcd m n))]

(int (/ (inc peri) p)))))</lang>