ホーム - Project Euler

Problem 63¶

Powerful Digit Counts¶

The $5$-digit number, $16807=7^5$, is also a fifth power. Similarly, the $9$-digit number, $134217728=8^9$, is a ninth power.

How many $n$-digit positive integers exist which are also an $n$th power?

べき乗の桁の個数¶

$5$桁の数 $16807=7^5$は自然数を5乗した数である. 同様に$9$桁の数 $134217728=8^9$も自然数を9乗した数である.

自然数を $n$ 乗して得られる $n$ 桁の正整数は何個あるか?

(import (scheme base)
        (gauche base)
        (scheme inexact))

(define (digit-num num)
  (assume (exact-integer? num))
  (assume (not (negative? num)))
  (if (zero? num)
    1
    (+ (floor->exact (log num 10))
       1)))

(define (powerful-digit-list)
  (let loop1 ([base 1]
              [rest (iota 9 1)]
              [result '()])
    (if (null? rest)
      (reverse result)
      (let loop2 ([index (car rest)]
                  [rest rest]
                  [result result])
        (cond
          [(< 9 index)
           (loop1 (+ base 1)
                  rest
                  result)]
          [(< (digit-num (expt index base)) base)
           (loop2 (+ index 1)
                  (delete index rest)
                  result)]
          [(= (digit-num (expt index base)) base)
           (loop2 (+ index 1)
                  rest
                  (cons `(,index . ,base) result))]
          [else
            (loop1 (+ base 1) rest result)])))))

(define answer-63
  (length (powerful-digit-list)))

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