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.