Euler 26 - recurring cycles

by @ardumont on 20 May 2013

Another euler problem about counting the greatest recurring cycle inside a fraction.

Problem 26 - http://projecteuler.net/problem=26 A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given: 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle. Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

As usual, we will add facts just below the functions to document the function.

take-while and 1

We need to be able to capture elements that satisfies the first element plus the first element which falsifies the predicate. So for this, we will use the standard take-while and add the next element. It's a take-while and 1.

(defn tw
  "'take-while pred coll' with the first element that wrong the predicate pred."
  [pred coll]
  (let [[h t] (split-with pred coll)]
    (concat h [(first t)])))

(m/fact
  (tw even? [0 2 4 6 8 9 10 11 12]) => [0 2 4 6 8 9]
  (tw even? [1 2 3 4])              => [1])

division

We compute the division as we learnt it in elementary school. We'll use the iterate function to benefit from lazyness.

(defn division
  "Compute the division the elementary school way :D (D is denominator, N numerator, R remains, Q quotient)."
  [N D]
  (->> {:c? true :n N}
       (iterate
        (fn [{:keys [n]}]
          (let [R (rem n D)
                Q (quot n D)]
            (cond (or (= 0 R) (= R D)) {:c? false :n 0        :q Q}
                  (< R D)              {:c? true  :n (* 10 R) :q Q}
                  :else                {:c? true  :n R        :q Q}))))
       (drop 1)))

(m/fact :now-we-have-a-way-to-divide-infinitely
  (->> (division 1 8)
       (tw :c?)
       (map :q)) => [0 1 2 5]
  (->> (division 1 20)
       (tw :c?)
       (map :q)) => [0 0 5]
  (->> (division 1 7)
       (take 20)
       (map :q)) => [0 1 4 2 8 5 7 1 4 2 8 5 7 1 4 2 8 5 7 1]
  (->> (division 1 7)
       (take 20)
       (map :n)) => [10 30 20 60 40 50 10 30 20 60 40 50 10 30 20 60 40 50 10 30]
  (->> (division 1 13)
       (take 20)
       (map :q)) => [0 0 7 6 9 2 3 0 7 6 9 2 3 0 7 6 9 2 3 0])

recurring-cycle-count

Now I want to be able to count the recurring cycles inside a sequence.

(defn recurring-cycle-count
  "Compute the size of a recurring cycle in a sequence."
  [s]
  (->> {:v s :m {} :i 0}
       (iterate
        (fn [{:keys [v m i] :as cp}]
          (let [[h & t] v
                p       (m h)]
            (if p
              (assoc cp :r (- i p))
              {:v t :m (assoc m h i) :i (+ 1 i)}))))
       (drop-while #(nil? (:r %)))
       first
       :r))

(m/fact
  (recurring-cycle-count [10 30 20 60 40 50 10 30 20 60 40 50 10 30 20 60 40 50 10 30]) => 6
  (recurring-cycle-count [0 1 4 2 8 5 7 1 4 2 8 5 7 1 4 2 8 5 7 1])                     => 6
  (recurring-cycle-count [0 1 2 3 4 1 2 3 4])                                           => 4
  (recurring-cycle-count [0 1 2 5 2 5 2 5])                                             => 2)

recurring-cycle

Now that We have a way to infinitely divide a number by another and a function to compute the recurring-cycle count, we can compute what we want and ensure it's ok according to the problem's facts.

For this, we can create a function which will divide the number by 1, then retrieve the sequence of rest from that division and compute the recurring cycle count from this sequence.

(def recurring-cycle ^{:doc "Compute the recurring cycle from a division by 1"}
  (comp recurring-cycle-count
        (partial map :n)
        (partial division 1)))

(m/tabular
 (m/fact
   (recurring-cycle ?n) => ?r)
    ?n ?r
    2  1
    3  1
    4  1
    5  1
    6  1
    7  6
    8  1
    9  1
    10 1
    13 6)

Result

So, from 0 to 1000, we compute the recurring cycle count for each number then determine the max. The number 983 is the number with the longest recurring-cycle 982.

(defn max-recurring-cycle
  "Given a limit l, return the couple [longest-recurring-cycle number] from 1 to (l-1), which corresponds to the number for which 1/number has the longest recurring cycle."
  [l]
  (->> (range 1 l)
       (map (juxt recurring-cycle identity))
       (into (sorted-map))
       last))
(m/fact
  (max-recurring-cycle 1000) => [982 983])

Some small check on time:

euler-lab.core26> (time (max-recurring-cycle 1000))
"Elapsed time: 237.337448 msecs"
[982 983]