[Project Euler] Problem 29 「個別のべき乗」

2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, ab を全て考えてみよう:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?

aとbの直積集合を求められれば答えは求まりそうです.

1. aとbの直積集合を求める.
2. aのb乗を求める.
3. 重複を取り除く.

手続きは次のようになります.

(require srfi/1)

;; 直積集合を求める.
(define (product list-a list-b)
  (apply append
         (map (lambda (a)
                (map (lambda (b) (list a b))
                     list-b))
              list-a)))

;; 重複した要素を取り除く
(define (make-set items)
  (define (loop ans rest)
    (cond ((null? rest) ans)
          ((find (lambda (a) (= (car rest) a)) ans) (loop ans (cdr rest)))
          (else (loop (cons (car rest) ans) (cdr rest)))))
  (loop '() items))

(define dp 
  (map (lambda (a) (apply expt a))
       (product (iota 99 2) (iota 99 2))))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (take dp 20)
(4
 8
 16
 32
 64
 128
 256
 512
 1024
 2048
 4096
 8192
 16384
 32768
 65536
 131072
 262144
 524288
 1048576
 2097152)
> (length (make-set dp))
9183
>