Project Euler Problem 73

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.