ホーム - Project Euler

Problem 56¶

Powerful Digit Sum¶

A googol ($10^{100}$) is a massive number: one followed by one-hundred zeros; $100^{100}$ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only $1$.

Considering natural numbers of the form, $a^b$, where $a, b \lt 100$, what is the maximum digital sum?

もっとべき乗の数字和¶

Googol ($10^{100}$)は非常に大きな数である: 1の後に0が100個続く. $100^{100}$は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも数字和 ( 桁の和 ) は$1$である.

$a, b \lt 100$ について自然数 $a^b$ を考える. 数字和の最大値を答えよ.

(import (scheme base)
        (gauche base))

(define (digit-sum num)
  (assume (exact-integer? num))
  (assume (not (negative? num)))
  (if (zero? num)
    0
    (let loop ([rest num] [result 0])
      (if (zero? rest)
        result
        (loop (div rest 10)
              (+ result
                 (mod rest 10)))))))

(define all-num
  (fold-right (^[n lis]
                (append
                  (map (^m `(,n ,m))
                       (iota 99 1))
                  lis))
              '()
              (iota 99 1)))

(define all-num&digit-sum
  (map (^[lis]
         `(,lis . ,(digit-sum
                     (expt (car lis)
                           (cadr lis)))))
       all-num))

(define max-digit-sum
  (fold (^[result current]
          (if (< (cdr result) (cdr current))
            current
            result))
        '(#f . 0)
        all-num&digit-sum))

(define answer-56
  (cdr max-digit-sum))

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