repeating-decimal.clj

(ns repeating-decimal)

(defn repeating-decimal [n]
  (loop [rem 1 rems #{} divs [] i 0]
    (let [div (int (/  (* rem 10) n))
          rem (mod  (* rem 10) n)]
      (if (and (not= rem 0) (contains? rems rem))
        [n divs]
        (when (not= rem 0)
          (recur rem (conj rems rem) (conj divs div) (inc i)))))))

(comment
  (repeating-decimal 7)
  (repeating-decimal 11)
  (repeating-decimal 12)
  (repeating-decimal 97)
  )

(defn solve [n]
  (loop [i n, m 0, divs []]
    (let [l (count divs)]
      (if (> i l)
        (let [divs' (repeating-decimal i)
              l' (count divs')]
          (if (> l' l)
            (recur (dec i) i divs')
            (recur (dec i) m divs)))
        [m divs]))))

;; (solve 100000)

• 1/nの循環節の長さはnを超えない
  • 同じ剰余が現れたら循環 ⇒ ありうる剰余は 0〜n-1のn通り
• つまり、たとえば10000以下の数nで1/nが10000以上の長さの循環節を持つことはない
• この性質を利用すれば、100000, 99999, 99998, ..., その時点の循環節の最大長 の範囲の数だけを探索すればいい
  • それ以上小さい値をチェックしても、より長い循環節をもつ数がないことが保証されるため