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

５００個以上の約数を持つ最小の三角数を求める。

まずは三角数の定義。

(defn triangle
  ([] (triangle 1 0))
  ([i n] (lazy-seq
           (cons (+ i n) (triangle (inc i) (+ i n))))))

次に約数の数え方だが、基本的に素因数分解して、各素数の指数＋１を掛け合わせると求められる。

なので素因数分解。

(defn prime-factors
  ([x] (prime-factors x 2))
  ([x i] (cond
           (= 1 x) []
           (< x (* i i)) [x]
           (zero? (rem x i)) 
               (lazy-seq (cons i (prime-factors (/ x i) i)))
           :else 
               (lazy-seq (prime-factors x (inc i))))))

素数をうまく定義してそれを利用すればより効率的にできそうだが、とりあえず簡単なアルゴリズムにとどめておく。

次に、指数（各素数の頻度）をとって１を足して掛け合わせる。

(defn divisor-count [n]
  (->> n
      (prime-factors)
      (frequencies)
      (vals)
      (map inc)
      (apply *)))

「約数がn個以下」という条件を読みやすく定義しておきたい。引数二つならそのまま評価するが、一つなら関数を返すようにしておく。

(defn less-than-n-divisors 
  ([n] (fn [x] (> n (divisor-count x))))
  ([n x] (> n (divisor-count x))))

あとは組み合わせるだけ。

(->> (triangle)
     (drop-while (less-than-n-divisors 500))
     (first))

ちなみに(divisor-count 1)は特殊ケースとして定義しないといけないかとも思ったのだが、(apply * ())が1に評価されるのでそのままでも大丈夫であった。あまり美しくないが。