Problem 92 - コラッツみたいな

メモ化が無いと辛そうかなと思ってたけど、メモ化しても辛かった。

各桁の数を2乗して足し合わせて新たな数を作ることによって、作られる数字の列を考える。
例えば
　　44 → 32 → 13 → 10 → 1 → 1
　　85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
のような列である。結果として1か89で無限ループに陥っている。
ここで、ある数から始めた列は1か89に到達することが分かっている。
では、10,000,000より小さい数で89に到達する数はいくつあるか。

なんかの数を分割して、二乗して足すと、1か89に収束する。

ふむふむ。コラッツ予想みたいな感じだね。

コラッツ不思議だ(これが言いたかっただけ)

で、89に到達する数を数えるんだけど、10,000,000^n回は絶対計算したくない訳。

そこで、メモ化が必要だと考えて、SICPを読み進めたんだけど、これでもかなりきつい。

(require (lib "69.ss" "srfi"))

(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 (problem92 n)
  (letrec ((square (lambda (n) (* n n)))
           (memoize (lambda (f)
                      (let ((table (make-hash-table)))
                        (lambda x
                          (let ((prev-result (and (hash-table-exists? table x)
                                                  (hash-table-ref table x))))
                            (or prev-result
                                (let ((result (apply f x)))
                                  (hash-table-set! table x result)
                                  result)))))))
           (collatz-like (memoize
                           (lambda (n)
                             (cond ((= n 1) 0)
                                   ((= n 89) 1)
                                   (else
                                     (collatz-like (apply + (map square (number->list n)))))))))
           (iter (lambda (n acc)
                   (if (zero? n)
                       acc
                       (iter (- n 1) (+ (collatz-like n) acc))))))
    (iter n 0)))

(problem92 100000)   ; 85623
(problem92 1000000)  ; 856929
(problem92 10000000) ; 8581146

一瞬でメモリを食い尽くす。お・恐ろしいぜ。

8割位は89に到達するっぽいので、何か法則があるっぽい。