42 lines
1.5 KiB
Common Lisp
42 lines
1.5 KiB
Common Lisp
;; Approach: put one point of the triangle at (0, 0), another at (a,
|
|
;; 0), and the last point at (x, y). Solve for x and then y, and the
|
|
;; area is: (b/4 * sqrt(4a^2 - b^2)). As an optimization, note that
|
|
;; (4a^2 - b^2) must be a perfect square to ensure a rational
|
|
;; solution.
|
|
;;
|
|
;; Note that SQRT is not accurate enough for this
|
|
;; problem. Fortunately, there is ISQRT (which is *not* the same as
|
|
;; (FLOOR (VALUES (SQRT N))) on SBCL, despite what CLHS says).
|
|
;;
|
|
;; Also note that this solution is very slow (takes a minute or so to
|
|
;; compute the answer).
|
|
|
|
(defun perimeter (a b)
|
|
"Returns the perimeter of a triangle with two sides of length A and one of length B"
|
|
(+ a a b))
|
|
|
|
(defun perfect-square-root (n)
|
|
"Returns the integer square of of N if N is a perfect square, otherwise returns NIL (note that this function can correctly handle very large integers)"
|
|
(loop for m upfrom (isqrt n)
|
|
for square = (square m)
|
|
until (> square n)
|
|
do (when (= square n)
|
|
(return m))))
|
|
|
|
(defun integer-area-p (a b)
|
|
"Determines if triangle with two sides of length A and one of length B has an integer area"
|
|
(let* ((c-squared (- (* 4 a a) (* b b)))
|
|
(c (perfect-square-root c-squared)))
|
|
(when c
|
|
(integerp (* b 1/4 c)))))
|
|
|
|
(defun almost-equilateral-triangles (&optional (limit 1000000000))
|
|
(loop for offset in '(-1 1)
|
|
sum (loop for a upfrom 2
|
|
for b = (+ a offset)
|
|
for perimeter = (perimeter a b)
|
|
while (<= perimeter limit)
|
|
sum (if (integer-area-p a b)
|
|
perimeter
|
|
0))))
|