Problem 23 - 2つの過剰数の和

結構大変だった。

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である.
真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
12は, 1+2+3+4+6=16となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.

方針はこんな感じ。

まず、過剰数を出す。
2つの過剰数の和を出す。12+12,12+18 ...
2つの過剰数の和で書き表せない正の整数の総和を求める。

問題は「2つの過剰数の和」。

過剰数はやたらいっぱい(6965個)あるので、2つの過剰数の和(6965^2個)を求めようと思って素直に組み合わせを求めたらメモリ不足になった。
色々やったけどダメで。
リストは順序づけられているので、高速化出来るはず。順序づけられたリストのunionと言えば・・・SICP!!

SICPを読む(72) 問題2.61 - 2.62 順序づけられたリストとしての集合 - ボクノス
↑コレのunion-setと、素因数分解divisorを使って、

define (problem23 n)
  (- (apply + (iota n 1))
     (apply + (let ((l (filter (lambda (a)
                                 (< (* 2 a)
                                    (apply + (divisor a)))) (iota n 1))))
                   (fold-right
                     (lambda (a acc)
                       (union-set
                         acc
                         (fold-right
                           (lambda (b seq)
                             (if (<= (+ a b) n)
                                 (cons (+ a b) seq)
                                 seq))
                           '() l)))
                     '() l)))))

(problem23 28123) ; 4179871

順序づけられたリストはえぇぇぇ。といっても20秒(過剰数15秒unionで5秒)くらいかかる。

追記

まだまだ全然早くなりそうだ。暇があったらやる。