Project Euler Problem 73

Ivar Thorson bio photo By Ivar Thorson

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.