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.