Project Euler Problem 73 continues the sequence of problems related to Farey Sequences. This time, we are asked to find the number of proper fractions between 1/3 and 1/2 with denominators less than 12,000.

I began by using code from problem 71 to compute the Farey Sequences.

;; Using code from Problem #71

(defn next-farey-element [[n a b c d]]
  (let [k (int (/ (+ n b) d))
        p (- (* k c) a)
        q (- (* k d) b)]
    [n c d p q]))

(defn make-farey-seq [n]
  (take-while #(< % 1)
              (map (fn [[n a b c d]] (/ a b))
                   (iterate next-farey-element [n 0 1 1 n]))))

(defn euler-73 []
  (->> (make-farey-seq 12000)   ;; 43 million entries
       (drop-while #(<= % 1/3))
       (take-while #(<  % 1/2))
       count))

(time (euler-73)) ;; "Elapsed time: 56203.952061 msecs"

While that’s technically within the 1 minute computation requirement, it’s a little close for comfort. Let’s try again with a different algorithm:

(use '[clojure.contrib.math :only (floor ceil)])

(defn gcd [a b] (if (zero? b) a (recur b (mod a b)))) 

(defn euler-73-faster []
  (let [lo 1/3
        hi 1/2
        lim 12000]
    (loop [d 2
           total 0]
      (if (> d lim)
        total
        (let [begin (floor (inc (* d lo)))
              end   (ceil  (dec (* d hi)))
              vals  (for [n (range begin (inc end))
                          :when (= 1 (gcd n d))]
                      n)]
          (recur (inc d) (+ total (count vals))))))))

(time (euler-73-faster)) ;; "Elapsed time: 6883.956757 msecs"

Ahh, that’s better.