Y箱

自分以外の約数の和がお互いの値になっているようなものの和を求める問題です。

約数の和は、約数を求めて足すのかなと思って調べてみたら、公式があった。
たとえば、ある数の素因数表示が
a^n * b^m
であったとすると、約数の和は
(1 + a + a^2 + .. + a^n) * (1 + b + b^2 + .. + b^m)
で表わせるんだそうな。 なるほどね。
この式を展開してみるとたしかにすべての約数が出てくるよね。

ってことで、1から順に数xを取って
xの約数の和 y
yの約数の和 z
x = z かつ、x != y
であるようなものだけ残してやるわけです。

で、前に作った、素数のリスト生成と素因数分解処理を持ってきて、
素因数分解の結果から、約数の和を求める関数を作った。

;;
;; Problem 21  : 2011/5/5
;;"Elapsed time: 1260.253748 msecs"

;; prime list

(def *prime-list* (atom []))

(create-prime-list-under 100000)

;; factors 
;; (foctors 12) => (2 2 3)


(defn multi-plus [lst]
  ;; multi-plus : (2 2 2) -> (+ 8 4 2 1)
  (if (empty? lst)
    1
    (+ (apply * lst) (multi-plus (rest lst)))))

(defn sum-of-divisor [n]
  (let [ ftr (factors n)]
    (- (reduce *
            (for [tgt (distinct ftr)]
              (multi-plus (filter #(= % tgt) ftr))))
       n)))


(reduce +
        (filter (fn [x] (let [y (sum-of-divisor x)
                              z (sum-of-divisor y)]
                          (and (= x z) (not (= x y)))))
                (range 2 10000)))

;;