Y箱

2つの五角数の和も差もまた五角数になるような組のうち、最小のものを求める問題。

基本的にしらみつぶし。
n番目の五角数について、(n-1)番目以前のそれぞれの五角数が条件に合うかどうか確認して、
最初にみつかったものを答えにしている。

五角数かどうかの判定は、n番目の五角数をxとすると
x=n(3n-1)/2
3n^2-n-2x=0
n=(1+sqrt(24x+1))/2
だから、24倍して1を足したものの平方根に1を足したものが2で割りきれるかどうかで判定。

;;
;; Problem 44  : 2011/6/13
;;"Elapsed time: 10744.530939 msecs"
;;
;; Memoized!!??
;; "Elapsed time: 38270.006104 msecs"           

(use 'clojure.contrib.math)

(defn pentagonal [n]
  (/ (* n (- (* 3 n) 1)) 2))

(defn pentagonal? [n]
  (zero? (rem (+ 1 (sqrt (+ 1 (* 24 n)))) 6)))

(take 1
(filter #(true? (first %))
        (mapcat (fn [num] 
                  (let [tgt (pentagonal num)]
                    (for [child-num (range (dec num) 0 -1)]
                      (let [child (pentagonal child-num)]
                        [(and (pentagonal? (+ tgt child))
                              (pentagonal? (- tgt child)))
                         tgt
                         child]))))
                (iterate inc 5))))