Project Euler Problem 23

問題23: 2つの過剰数の和で書き表せない正の整数の総和を求めよ.(28123より大きい整数は2つの過剰数の和で表せることがわかっている）。[=>問題文]
　だんだん手ごたえのある問題になってきましたね。

問題23の解答

math-lib はこちら。

;; Emacs Lisp
(require 'math-lib) ; primes-sieve, get-divisors
(require 'cl)

(defun problem023 (n)
  (let* ((abundant-numbers  (make-vector n 0))
         (last-aset-index 1)
         (primes (primes-sieve (1+ (truncate (sqrt n)))))
         ;; 真の約数の和を計算する関数
         (sum-of-divisors
          (lambda (n)
            (- (apply #'+ (get-divisors n primes)) n)))
         ;; 2つの過剰数の和で表せるかチェックする関数
         (sum-of-abundants-number-p
          (lambda (n)
            (let* ((result nil)
                   (i 2)
                   (j last-aset-index)
                   (ni (aref abundant-numbers i))
                   (nj (aref abundant-numbers j)))
              (while (and (null result) (<= i j))
                (let ((sum (+ ni nj)))
                  (cond
                   ((< sum n) (setq ni (aref abundant-numbers (incf i))))
                   ((> sum n) (setq nj (aref abundant-numbers (decf j))))
                   (t (setq result t)))))
              result))))
    ;; メインループ
    (do ((k 1 (1+ k)) (ans 0))
        ((> k n) ans)
      (unless (funcall sum-of-abundants-number-p k)
        (incf ans k))
      ;; 過剰数ならば vector へ追加
      (if (< k (funcall sum-of-divisors k))
          (aset abundant-numbers (incf last-aset-index) k)))))

(problem023 28123)

　配列 abundant-numbers に順に過剰数を保存してゆきます。これを使って「2つの過剰数の和」で表せるかどうかの判定します。判定関数 sum-of-abundants-number-p では、インデックス i を abundant-numbers の先頭からインクリメント、j を(nより小さい過剰数の)末尾からデクリメントしてゆき、それらが指し示す2数の和を n に近づけていきます。(> i j) となったら該当する過剰数のペアは存在しません。なお判定処理のインデックス移動の都合から、abundant-numbers の最初の2要素は 0 固定で、インデックス2から過剰数を埋めています。
　今回 Core2 Quad 6600 と Pentium4(PrescottNorthwood)コアのCeleronで試してみました。結果は順に 3.8秒と 75.8秒。ハードウェアの差が大きく反映されました。 うそでした、多分Celeronマシンは byte-comile してなかったのかな。改めて計測しなおしました。

Function     Avg(sec)    CPU
==========   ========   =======================
problem023   3.766000   Core2 Quad 6600 2.4GHz
problem023   9.170000   Celeron (Pentium4 Northwood コア) 2.4GHz

　それでも同じクロック数であるにもかかわらず 約 2.4 倍の差が出ました。キャッシュ差かマルチコアの能力か。