Project Euler Problem 72

Ivar Thorson bio photo By Ivar Thorson

My solution to Project Euler Problem 72 is rather simple. We are asked to find the length of a Farey Sequence for all fractions with denominators less than one million.

Wikipedia’s page on the Farey Sequence gives us the property we need to solve this problem: a relationship between Euler’s Totient function and the length of a Farey Sequence. Reusing the euler-totient function from problem 69 and the solution was just a few lines:

(defn farey-seq-length [n]
  (reduce + (map euler-totient (range 1 (inc n)))))

(time (farey-seq-length 1000000)) ;; "Elapsed time: 36900.410736 msecs"

There is doubtless a much, much faster way to accomplish this, but I haven’t the time for a better analysis of the problem today. Besides, I was looking for an excuse to use that euler-totient function from problem 69…