Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 29]]

## Distinct Powers

<p>Consider all integer combinations of $a^b$ for $2 \le a \le 5$ and $2 \le b \le 5$:</p>

\begin{matrix}

2^2=4, &2^3=8, &2^4=16, &2^5=32\\

3^2=9, &3^3=27, &3^4=81, &3^5=243\\

4^2=16, &4^3=64, &4^4=256, &4^5=1024\\

5^2=25, &5^3=125, &5^4=625, &5^5=3125

\end{matrix}

If they are then placed in numerical order, with any repeats removed, we get the following sequence of $15$ distinct terms:

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

How many distinct terms are in the sequence generated by $a^b$ for $2 \le a \le 100$ and $2 \le b \le 100$?

## 個別のべき乗

<p>$2 \le a \le 5$ と $2 \le b \le 5$ について, $a^b$ を全て考えてみよう:</p>

\begin{matrix}

2^2=4, &2^3=8, &2^4=16, &2^5=32\\

3^2=9, &3^3=27, &3^4=81, &3^5=243\\

4^2=16, &4^3=64, &4^4=256, &4^5=1024\\

5^2=25, &5^3=125, &5^4=625, &5^5=3125

\end{matrix}

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

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

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

```scheme

(import (scheme base)

        (gauche base)

        (scheme sort))

(define (unique lis)

  (let loop ([prev #f] [rest lis] [result '()])

    (cond

      [(null? rest) (reverse result)]

      [(and prev

            (= prev (car rest)))

       (loop prev (cdr rest) result)]

      [else

        (loop (car rest)

              (cdr rest)

              (cons (car rest) result))])))

(define (powers a b)

  (assume (exact-integer? a))

  (assume (exact-integer? b))

  (assume (<= 2 a))

  (assume (<= 2 b))

  (fold (^[a lis]

          (append (fold (^[b lis]

                          (cons (expt a b) lis))

                        '()

                        (iota (- b 1) 2))

                  lis))

        '()

        (iota (- a 1) 2)))

(define answer-29

  (length (unique (list-sort < (powers 100 100)))))

(format #t "29: ~d~%" answer-29)

```