Euler : Problem 26

Posted by YpsilonTAKAI On 2011年5月11日水曜日 0 コメント
循環小数の循環列の問題。

なにしろわからなかったから、調べてみると、おもしろいねぇ。

・循環列の長さは最大でも「最大の約数-1」らしい。
   ってことは、素数だけ気にしてればいい。

・素数nの場合、1/nの循環列の長さkは
   10^kをnで割ったあまりが1である最小のk

ということで効率よく求められそう。

今回の答えは、下のloopの length-prime-list に束縛したリストを
10個ぐらい計算してみたところで分っていたので、本来はこれだけでOK。
ちゃんとたしかめようとするとちょっと面倒ってところ。

;;
;; Problem 26 : 2011/5/11
;; "Elapsed time: 63.869011 msecs"
(def *prime-list* (atom []))
(create-prime-list-under 1000)


(loop [length-prime-list (for [n (reverse @*prime-list*)]
(list (first (filter #(= 1 (rem (expt 10 %) n)) (range 1 n)))
n))
old-len 0
old-prim 0]
(let [[length prime] (first length-prime-list)]
(cond (> old-len prime) [old-len old-prim]
(< old-len length) (recur (rest length-prime-list) length prime)
:else (recur (rest length-prime-list) old-len old-prim))))

;;

0 コメント:

コメントを投稿