Y箱

循環小数の循環列の問題。

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

・循環列の長さは最大でも「最大の約数-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))))

;;