November 29, 2008

A Pythagorean triplet is a set of three natural numbers, a b c, for which a2 + b2 = c2.

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

A brute-force solution in Common Lisp:

(defun sqrd (x)
(* x x))

(defun pythag-trip-p (a b c)
"Tests if a b and c satisfies the pythagorean equation"
(eq (sqrd c)
(+ (sqrd a) (sqrd b))))

(defun sum-eq-1000-p (a b c)
"Tests if the sum equals 100"
(= 1000 (+ a b c)))

(defun euler-9 ()
(let ((result nil))
(loop for a from 1 to 1000 until (not (null result)) do
(loop for b from 1 to 1000 until (not (null result)) do
(let ((c (sqrt (+ (sqrd a) (sqrd b)))))
(when (sum-eq-1000-p a b c)
(print (list a b c))
(setf result (list a b c))))))
(apply #'* result)))