Problem 40 - チャンパーノウン定数

案外ムズイかと思って放置してた問題。

Problem 40 - PukiWiki

正の整数を順に連結して得られる以下の10進の無理数を考える:

0.123456789101112131415161718192021...

小数点第12位は1である.

dnで小数点第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.

わからない時は、

「ナイーブに逝け」

という格言に従い、とっても普通に1個づつ進めてみた。

(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 (problem40 n)
  (letrec ((iter (lambda (i next m l)
                   (cond ((= next (expt 10 n)) '())
                         ((null? l) (iter i next (+ m 1) (number->list (+ m 1))))
                         ((= i next) (cons (car l) (iter i (* next 10) m l)))
                         (else
                           (iter (+ i 1) next m (cdr l)))))))
    (apply * (iter 1 1 1 '(1)))))

(problem40 7) ; (1 1 5 3 7 2 1)
(problem40 7) ; 210

スゲー無駄なのはわかるんだけど、どう早くするか・・・１万倍は早くなると思うんだよ。

落ち着いて考えてみる。