# euler 39 integer right triangles

Mar 20, 2015

Straightfoward, this. An interesting insight into speed difference between `SBCL` and `Clozure`: the former took 0.75 seconds to run this, while the latter took about 4 seconds (without the type annotations, `SBCL` takes 33 seconds).

``````(defun is-right-triangle (n1 n2 n3)
(declare (type fixnum n1 n2 n3))
(= (+ (expt n1 2) (expt n2 2)) (expt n3 2)))

(defun triangle-solutions (n)
(declare (type fixnum n))
;; Largest side (hyp) can't be less than a third of the total
(loop for hyp from (floor (/ n 3)) upto (- n 2)
;; Avoid repeating combinations, so WLOG let one side
;; be greater than the other
for sides-sum = (- n hyp)
when (loop for side1 from (ceiling (/ sides-sum 2)) to (1- sides-sum)
for side2 = (- sides-sum side1)
when (is-right-triangle side1 side2 hyp)
collect (list side1 side2 hyp))
collect it))

(defun max-triangle-solutions (n)
(declare (type fixnum n))
;; n cannot be less than 3
(let* ((solutions (loop for i from 3 to n
collect (length (triangle-solutions i))))
(max-solution (loop for elem in solutions maximizing elem)))
(cons max-solution (+ 3 (position max-solution solutions)))))
``````

The answer needed is given by `(max-triangle-solutions 1000)`, while any specific solution can be got by (e.g.) running `(triangle-solutions 120)` which yields `(((40 30 50)) ((45 24 51)) ((48 20 52)))`