Project Euler #021 – 友愛数

15 1月 2010

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

日本語訳：

n の真の約数の合計を d(n) と定義する。
（真の約数とは整数 n の約数で n 以外のものである）

もし d(a) = b かつ d(b) = a が a ≠ b で成立するならば a と b は友愛数と呼ばれる。

たとえば220の真の約数は 1,2,4,5,10,11,20,22,44,55,110 で
d(220) = 284 であり、284の真の約数は 1,2,4,71,142 なので
d(284) = 220 となる。

10000未満の友愛数の合計を求めよ。

以前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
 
def sum_of_divisors(n)
  divisor(n)[0..-2].inject(:+)
end
 
sum = 0
 
(1...10000).each do |n|
  sod = sum_of_divisors(n)
  next if sod.nil?
  next if n == sod
  sum += n if n == sum_of_divisors(sum_of_divisors(n))
end
 
p sum

約数の和は prime_division で素因数分解したものから約数リストを生成して、最後の要素を除いたものを inject で合計してます。

さてClojureでは：

(ns euler.p021
  (:use clojure.contrib.seq-utils))
 
(defn prime-division
  "Return prime factors of N."
  [number]
  (loop [n number d 2 factors []]
    (cond (<= n d) (frequencies (conj factors d))
	  (zero? (rem n d)) (recur (/ n d) d (conj factors d))
	  :else (recur n (inc d) factors))))
 
(defn exp-prime-factor
  "Expand prime factor exponentially.
   Usage: (exp-prime-factor prime-factor index)
   Example: (exp-prime-factor 3 4) -> [1 3 9 27 81]"
  [pf idx]
  (map #(apply * (replicate % pf)) (range (inc idx))))
 
(defn composite-factors
  "Composite factors collection.
   Usage: (composite-factors coll [prime-factor index])
   Example: (composite-factors [1 2 4] [5 2])
            -> (1 2 4 5 10 20 25 50 100)"
  [last-coll coll]
  (for [x (apply exp-prime-factor coll)
	y last-coll]
    (* x y)))
 
(defn sum-of-proper-divisors
  "Return sum of proper divisor of N."
  [n]
  (apply + (drop-last
	    (reduce composite-factors [1] (prime-division n)))))
 
(def sum-of-proper-divisors (memoize sum-of-proper-divisors))
 
(defn amicable?
  "Return true if N has amicable pair."
  [n]
  (let [candidate (sum-of-proper-divisors n)]
    (if (not= candidate n)
      (= n (sum-of-proper-divisors candidate)))))
 
(println "Answer : "
	 (apply + (filter amicable? (range 10000))))

うわー、なんか長くなった。

Clojureコーディング規約・訳より

匿名関数は1行で収まる簡単な定義のみに使う。

ということで、素因数分解から約数のリストを生成する工程を幾つかの関数に切り分けたのが原因。

そして関数の名付けがむずかしくてドキュメントで補足するハメに・・。
まだまだ未熟よのう。

ためしに1関数にまとめてみたらこうなった。

(ns euler.p021
  (:use clojure.contrib.seq-utils))
 
(defn prime-division
  "Return prime factors of N."
  [number]
  (loop [n number d 2 factors []]
    (cond (<= n d) (frequencies (conj factors d))
	  (zero? (rem n d)) (recur (/ n d) d (conj factors d))
	  :else (recur n (inc d) factors))))
 
(defn sum-of-proper-divisors
  "Return sum of proper divisor of N."
  [n]
  (apply + (drop-last
	    (reduce (fn [m-coll coll]
	       (mapcat (fn [m-factor]
		  (map (fn [idx]
		     (* m-factor (. (bigint (first coll)) pow idx)))
		   (range (inc (second coll)))))
		m-coll))
	     [1] (prime-division n)))))
 
(def sum-of-proper-divisors (memoize sum-of-proper-divisors))
 
(defn amicable?
  "Return true if N has amicable pair."
  [n]
  (let [candidate (sum-of-proper-divisors n)]
    (if (not= candidate n)
      (= n (sum-of-proper-divisors candidate)))))
 
(println "Answer : "
	 (apply + (filter amicable? (range 10000))))