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…