Project Euler Problem 26 asks us to find number d where 1/d gives the longest recurring cycle of digits. Obviously, since some numbers (such as 1/3) repeat forever when written in decimal form, a lazy solution that takes digits one by one is a good idea here.

The intuitive way solve this problem is to realize that if we ever reach a point where the quotient and remainder are the same as a previously computed value, then we have reached the end of the repeating pattern of digits and further computation of digits will simply repeat what has come before.

In my first solution, I used several functions from previous problems max-at from problem 14, and first-where from problem 25. I reprint them here:

(defn first-where [condition seq]
  "Returns index of the first item in seq that satisfies condition."
  (loop [n 0
         r seq]
    (if (or (nil? r)
            (condition (first r)))
      n
      (recur (inc n) (next r)))))

(defn max-at [s]
  "Returns [xi x], where xi is the index number of the max element,
  (indexed from 1) and x is the max of s."
  (letfn [(find-max [s n x xi]
             (let [f (first s)
                   r (rest s)]
               (if (nil? f)
                 [xi x]
                 (if (> f x)
                   (recur r (inc n) f n)
                   (recur r (inc n) x xi)))))]
    (find-max s 1 0 0)))

From there it was a short step to solving this problem:

(defn div-digits [num den]
  "Returns a lazy lists of decimal digits of the num divided by den."
  (iterate (fn [[q r]]
             [(quot (* r 10) den) (rem (* r 10) den)])
           [(quot num den) (rem num den)]))

(defn duplicate-length [num den]
  "Returns the length of the repeating pattern, if any, in the decimal
  representation of num divided by den."
  (loop [digits (div-digits num den)
         ret []]
    (let [d (first digits)
          idx (first-where #(= d %) ret)]
      (if (< idx (count ret))
        (- (count ret) idx)
        (if (and (zero? (nth d 0)) (zero? (nth d 1)))
          0
          (recur (next digits) (conj ret d)))))))

(defn euler-26 []
  (let [[a b] (max-at (map #(duplicate-length 1 %) (range 2 10000)))]
    (inc a)))

The above solution works and is moderately fast. However, someone named “sammay” posted an even better algorithm on clojure-euler which exploits the properties of repeating decimals that was not intuitively obvious to me without reading the mathworld page to which sammay linked. I reprint sammay’s solution here because of its surprising simplicity:

;; calculate the multiplicative order of a modulo n
(defn order [a n]
  (first (filter #(= 1 (.modPow (bigint a) % (bigint n)))
         (map bigint (iterate inc 1)))))
 
;; remove factors of 2 and 5 and find the multiplicative order
(defn decimal-period [n]
  (cond (= 1 n) 0
    (zero? (rem n 2)) (decimal-period (/ n 2))
    (zero? (rem n 5)) (decimal-period (/ n 5))
    true (order 10 n)))
 
(defn p26 [n]
  (let [nums (range 1 n)
        periods (map decimal-period nums)]
    ((zipmap periods nums) (apply max periods))))

I think this is the first time I have seen an idiom using zipmap, so I found this solution particularly educational for both mathematics and programming in Clojure.