Problem 56 - Google

そういえば、googleって数の大きさだったっけ。

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

a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.

力づくなら簡単なんだけど。

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))

(define (problem56 n)
  (letrec ((iter (lambda (a b sum)
                   (cond ((zero? a) sum)
                         ((zero? b) (iter (- a 1) n sum))
                         (else
                           (let* ((x (expt a b))
                                  (s (apply + (number->list x))))
                             (iter a (- b 1)
                                   (if (> s sum)
                                       s
                                       sum))))))))
    (iter (- n 1) (- n 1) 0)))

(problem56 100) ; 972

100^2回の演算回数を必要としてしまう。

100から下っていけば、答えはすぐに求まるはずなので、終了条件をどう絞るかというのがポイントになるみたい。

ちと考えてみる。

終了条件を絞る

a^bが、999だとすると、数値の合計は27になる。つまり、合計が28なら4桁以上であることがわかる。

処理すべき桁数がわかるので、処理を打ち切って、次に進む事が出来る。

(define (problem56 n)
  (letrec ((iter (lambda (a b sum)
                   (let* ((x (expt a b))
                          (s (apply + (number->list x))))
                     (if (< (/ (log x) (log 10)) (/ sum 9))
                         (if (= b n)
                             sum
                             (iter (- a 1) n sum))
                         (iter a (- b 1)
                               (if (> s sum)
                                   s
                                   sum)))))))
    (iter (- n 1) (- n 1) 0)))

(problem56 100) ; 972

かなり絞れたけど、まだまだ重い。

追記

うほ。いい突っ込み。

それは微妙に違います
10^100を表す数の単位は「ぐーごる」(googol)です。

師匠ありがとう!!