Arantium Maestum

プログラミング、囲碁、読書の話題

Clojure入門 - Project Eulerを解いてみる 問23

第二十三問

過剰数の和として表せないすべての数字の和を求める。

とりあえず問題文に出てきた、過剰数の和として表せない数字の上限(それ自体は過剰数の和として表せるけど)を定数として定義。

(def MAX-NON-ABUNDANT-SUM 28123)

問21で出てきたdivisors関数をまた使う。

(def divides? (comp zero? rem))

(defn divisors [n]
  (->> (range (Math/sqrt n))
       (map inc)
       (filter #(divides? n %))
       (mapcat (fn [x] [x (/ n x)]))
       (into (sorted-set))
       drop-last))

これを使って過剰数か否かを調べる関数を作成。

(defn divisors-sum [n]
  (apply + (divisors n)))

(defn is-abundant [n]
  (< n (divisors-sum n)))

上限以下のすべての過剰数を算出し、それら二つの和を集合として作成。

(def abundance
  (filter is-abundant (range 1 MAX-NON-ABUNDANT-SUM)))

(def abundant-sums
  (set
    (for [x abundants
          y abundants]
      (+ x y))))

ここが一番重い。O(N2)になってしまっているのが嫌。

あとは、上限までの数字すべてから、その集合に含まれていないものを摘出して足し合わせるだけ。

(defn abundant-sum? [n]
  (contains? abundant-sums n))

(def non-abundant-sums
  (remove abundant-sum? (range 1 MAX-NON-ABUNDANT-SUM)))

(apply + non-abundant-sums)

filterの逆のremoveをはじめて使った。(filter (complement predicate))とどっちがいいだろうか。名前はfilter-notとかの方がわかりやすい気もする。if-notとかとも対応するし。