[Project Euler] Problem 16 「べき乗の数字和」

2¹⁵ = 32768 であり, これの各桁の和は 3 + 2 + 7 + 6 + 8 = 26 となる.
同様にして, 2¹⁰⁰⁰ の各桁の和を求めよ.

素直に, 2の1000乗を求めて, 各桁の和を求めます. 使用する手続きは次のようになります.

(require srfi/1)

(define (square x) (* x x))

(define (fast-expt-iter b n p)
  (cond ((= n 0) p)
        ((even? n) (fast-expt-iter (square b) (/ n 2) p))
        (else (fast-expt-iter b (- n 1) (* b p)))))

(define (fast-expt b n)
  (fast-expt-iter b n 1))

(define (decimal-format nbr)
  (define (loop ans n)
    (if (= 0 n)
        ans
        (loop (cons (remainder n 10) ans) (quotient n 10))))
  (loop () nbr))

手続きfast-exptについては, SICPを参考にしています. 計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (fast-expt 2 1000)
1071508607186267320948425049060001810561404811705
5336074437503883703510511249361224931983788156958
5812759467291755314682518714528569231404359845775
7469857480393456777482423098542107460506237114187
7954182153046474983581941267398767559165543946077
0629145711964776865421676604298316526243868372056
68069376
> (apply + (decimal-format (fast-expt 2 1000)))
1366
>