problem 39

三角形の周辺長が p(< 1000) の直角三角形の辺を a, b, c としたとき各辺が整数になる a, b, c の組の数がいちばん多い p を求める問題です。

cartesian-product を使って総当たりでチェックしているために時間はかかりますが答えは求まります。

(use srfi-1)
(use util.combinations)

(define (square x) (* x x))
(define (right-angle? t)
  (= (+ (square (car t))
        (square (cadr t)))
     (square (caddr t))))

(define (lookup n)
  (delete-duplicates
    (filter-map (lambda (t)
                  (let* ((a (car t))
                         (b (cadr t))
                         (c (- n a b))
                         (t (sort (list a b c))))
                    (if (and (> c 0) (right-angle? t))
                      t
                      #f)))
                (cartesian-product (list (iota (- n 1) 1) (iota (- n 1) 1))))))

(define (p39)
  (let loop ((i 3) (r 0) (p 0))
    (if (= i 1000)
      p
      (let* ((found (lookup i))
             (result (length found)))
        (loop (+ i 1)
              (if (> result r) result r)
              (if (> result r) i p))))))
(print (p39)