I don’t know how I managed to avoid learning about the properties of continued fractions in school; I can only blame the textbook authors for not including the material. Continued fractions are really quite remarkable; have you ever wondered why some rational fractions (e.g. 1/3) take infinitely many decimals to represent (0.3333…), while other fractions (e.g. 1/4) have a finite representation (0.25)? Or why if you represent these fractions in a different base (e.g. hexadecimal) then they may take a different finite or even infinite number of digits to represent?

Continued fractions give a mathematically pure way to describe rational fractions that isn’t dependent on some particular base counting system. Even more amazingly to me, many ‘irrational’ numbers such as square roots become repeating patterns when represented as continued fractions! Surely this says something fundamental about the nature of square roots, perhaps they are a very simple type of irrational number.

Problem 64 asks us to find the quantity of numbers under 1000 whose square roots have an odd-length period. My first approach was to use a mathematically simple definition and general definition:

(defn continuous-fraction
  "Returns a sequence of the coefficicents of the continuing fraction
  that is equivilent to n."
  [n]
  (rest (iterate (fn [[x i]]
                   (if (= i (int i))
                     [i 0]
                     [(int i) (/ 1 (- i (int i)))]))
                 [0 n])))

(take 10 (continuous-fraction (sqrt 2)))

Unfortunately for this simple definition, if you look at the sequence it generates, you can see numerical noise creep into the remainder. This would prevent us from easily testing whether the sequence is repeating or not in a manner similar to what we did in problem 24.

Still, if we use an algorithm similar to the famous Euclidean Algorithm for finding the greatest common divisor, we can write a sequence generator that does not suffer from numerical precision problems.

(use '[clojure.contrib.math :only (sqrt)])

(defn continued-fraction-sqrt
  "Returns a sequence of the coefficicents of the continued fraction
  that is equivilent to the square root of n, which must not be a simple square."
  [n]
  (iterate (fn [[a m d]]
             (let [m+ (- (* d a) m)
                   d+ (/ (- n (* m+ m+)) d)
                   a+ (int (/ (+ m+ (sqrt n)) d+))]
               [a+ m+ d+]))
           [(int (sqrt n)) 0 1]))

(defn period-length
  "Returns the length of the periodic sequence found in coll, or nil if the
  end of the sequence is reached without a pattern being found. "
  [coll]
  (loop [m {}
         i 0
         c coll]
    (and (seq c)
         (let [k (first c)]
           (if-let [v (m k)] 
             (- i v)
             (recur (assoc m k i)
                    (inc i)
                    (next c)))))))

(defn square? [n]
  (= n (* (int (sqrt n)) (int (sqrt n)))))

(defn euler-64 []
  (count (filter odd? (map #(period-length (continued-fraction-sqrt %))
                           (remove square? (range 1 10000))))))

(time (euler-64)) ;; "Elapsed time: 867.320304 msecs"

All in all, a rather mathematically interesting problem!