Problem 63 - n乗してn桁

Scheme

落ち着いて範囲を考える。


Problem 63 - PukiWiki


n乗してn桁になる数はいくつあるか。


ふむふむ。適当に計算してみる。


まず終端。

10^1は2桁,10^2は3桁,10^3は4桁・・・となるので、10^nはn乗するとn+1桁。絶対に追いつかない。

10以上は除外できる。


小さいループを。

1^1 1桁 OK。1^2 1桁 ダメ。
2^1 1桁 OK。2^2 1桁 ダメ。
..
4^1 1桁 OK。4^2 2桁 OK。4^3 2桁 ダメ。
...

どうやら1桁目から順に解いていけばいいみたいだ。桁が下回ったら追いつけない。


ということで、

(define (problem63)
  (letrec ((iter
             (lambda (a n)
               (cond ((= a 10) 0)
                     ((= (string-length (number->string (expt a n))) n)
                      (+ 1 (iter a (+ n 1))))
                     (else
                      (iter (+ a 1) 1))))))
    (iter 1 1)))

(problem63) ; 49

簡単！