[Project Euler] Problem 9 「特別なピタゴラス数」

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a² + b² = c²

例えば, 3² + 4² = 9 + 16 = 25 = 5² である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

ピタゴラス数を漏れ無く求めることが必要です.

1. 指定した範囲のピタゴラス数を求めます.
2. 3つの数の和を求めます.
3. 和でソートします.
4. 和が1000になっているピタゴラス数を探します.

手続きを定義します.

(require srfi/1)

(define (range lower upper)
  (if (<= lower upper)
      (iota (+ 1 (- upper lower)) lower)
      ()))

(define (pythagorean? a b c)
  (= (+ (* a a)
        (* b b))
     (* c c)))

(define (pythagorean-list upper)
  (apply append
         (map (lambda (a)
                (apply append
                       (map (lambda (b)
                              (filter-map (lambda (c)
                                            (and (pythagorean? a b c)
                                                 (list a b c)))                                          
                                          (range b (- upper (+ a b)))))
                            (range a (- upper a)))))
              (range 1 upper))))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (pythagorean-list 20)
((3 4 5))
> (sort (map (lambda (x) (list (fold + 0 x) x))
                (pythagorean-list 1000))
        (lambda (a b) (< (car a) (car b))))
((12 (3 4 5))
 (24 (6 8 10))
 (30 (5 12 13))
 (36 (9 12 15))
 (40 (8 15 17))
 (48 (12 16 20))
 (56 (7 24 25))
 (60 (10 24 26))

 ... 省略 ...

 (988 (266 312 410))
 (990 (99 440 451))
 (990 (165 396 429))
 (990 (180 385 425))
 (990 (264 315 411))
 (992 (31 480 481))
 (996 (249 332 415))
 (1000 (200 375 425)))
> (+ 200 375 425)
1000
> 

素数夜曲には, ピタゴラス数を次々と求める方法が紹介されていますが, ３辺の和が1000未満のピタゴラス数をすべて求められるわけではありません. 素数夜曲の方法でもこの問題の解は見つかりますが, それはタマタマです.