Euler : Problem 44

Posted by TAKAIY On 2011年6月29日水曜日 0 コメント
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))))

0 コメント:

コメントを投稿