Euler : Problem 12

Posted by TAKAIY On 2011年4月14日木曜日 0 コメント
三角数に関する問題。 だけど、三角数の性質とは関係ないのかな?

始めは逆の探索で、約数が500個以上ある数を求めて、それが三角数かどうか確認するって方法をやろうとしたんだけど、挫折した。三角数かどうか確認する関数も作ったけど、使わなかった。挫折した方法のときに必要だね。
結局、小さいほうから全調べ方式。

いつかリベンジしてやる。

factorsは前につくったやつで、そこで素数の一覧も使ってる。
時間には素数を作る時間は入ってない。

三角数を作る方法を2通り試したけど、とくに時間は変らないみたい。



;;
;; Problem 12 : 2011/4/14
;; "Elapsed time: 1954.309557 msecs"
;; pre defined func : factors [n]
;; (foctors 12) => (2 2 3)


;; count divisor
;; when n = f1^a * f2^b * ... * fn^x
;; divisor count = (a+1)*(b+1)* ... (x+1)
(defn count-divisor [n]
(let [ ftr (factors n)]
(reduce *
(for [tgt (distinct ftr)]
(inc (count (filter #(= % tgt) ftr)))))))


;; nth triangle num
(defn nth-triangle-num [n]
(/ (* n (inc n)) 2))


(loop [n 1]
(let [triangle-num (nth-triangle-num n)
divisor-num (count-divisor triangle-num)]
(if (> divisor-num 500)
(list n triangle-num divisor-num)
(recur (inc n)))))

;; triangle num seq
;;"Elapsed time: 1933.932106 msecs"
(defn triangle-num
([] (tri 2 1))
([n sum]
(lazy-seq
(cons sum (tri (inc n) (+ n sum))))))

(loop [triangle-num-list (triangle-num)]
(if (> (count-divisor (first triangle-num-list)) 500)
(first triangle-num-list)
(recur (rest triangle-num-list)))))


;; did not use
;; check triangle num
(defn triangle-num? [n]
(let [double-square-int (int (sqrt (* n 2)))
num-1 double-square-int
num-2 (inc num-1)]
(= (/ (* num-1 num-2) 2) n)))

;;

0 コメント:

コメントを投稿