Project EulerをClojureでおさらいシリーズ。
Problem 12

オリジナルはこちら

日本語訳：

三角数の数列は自然数の和で生成される。

7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。

よって最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

となる。

三角数の最初の7項について約数を挙げてみよう。

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

約数の数が5を越える最初の三角数は28であることがわかる。

約数の数が500を越える最初の三角数を求めよ。

約数の数を求めるアルゴリズムをどうするかの問題。

以前Rubyで解いたバージョンはこちら：

#!/usr/bin/env ruby
 
require 'mathn'
 
def divisor(n)
  result=[1]
  n.prime_division.each do |i|
    result = result + result.map {|x| (1..i[1]).map{|n| x*(i[0]**n)}}.flatten
  end
  result.flatten.sort
end
 
n = 1
tri = 1
begin
  n += 1
  tri += n 
end while divisor(tri).size <= 500
 
p tri

横着してmathnライブラリを使っています。

馬鹿正直に約数をすべて求めています、なんでこんなことしてたんだろ？？ ものすごくムダなことを・・・しかもソートしてるしｗ

案の定、遅いです。

さて、Clojureで書いてみます。

(ns euler.p012
  (:use clojure.contrib.seq-utils))
 
(def triangular-nums
  (lazy-cat [0] (map + triangular-nums (iterate inc 1))))
 
(defn prime-factors
  "Return prime factors of N."
  [number]
  (loop [n number d 2 factors []]
    (cond (<= n d) (conj factors d)
	  (= 0 (rem n d)) (recur (/ n d) d (conj factors d))
	  :else (recur n (inc d) factors))))
 
(defn num-of-divisors
  "Return numbers of divisors N has."
  [n]
  (apply * (map #(inc (nth % 1))
		(frequencies (prime-factors n)))))
 
(println "Answer : "
	 (first (filter #(> (num-of-divisors %) 500)
			(drop 2 triangular-nums))))

prime-factors は Project Euler #003 の largest-prime-factor の変形です。

7項目三角数、28を例に流れを解説すると

prime-factors は素因数に分解
例： 28 → [2 2 7]

frequencies は登場する要素を[要素 出現数]でまとめる関数。
clojure.contrib.seq-utils に含まれています。
例： [2 2 7] → [[2 2] [7 1]]

num-of-divisors で約数の組み合わせの数を計算しています。
例： (2+1) * (1+1) → 6

triangular-nums は三角数を生成する遅延シーケンス。
三角数は n(n+1)/2 でも求められます。
n と (n+1) は連続しているので、それを利用するとさらに計算量が減らせそうですね。