Irrational square roots of integers may be represented by continued fractions. An example is:

                           1
  sqrt[23] = 4 + -------
                         1 +  1
                              -------
                              3 +   1
                                     --------
                                     1 +  1
                                           --------
                                           8 + ...

The leading fractional terms: 1,3,1,8 repeat infinitely and the
result is expressed with the notation: sqrt[23] = [4;(1,3,1,8)] with
period 4.

The expansion above is derived recursively by:

sqrt[23] = 4 + sqrt[23] - 4 = 4 + 1/ { 1/(sqrt[23]-4) }, and

a0 = 4, 1/(sqrt[23]-4) =  (sqrt[23]+4)/7   = 1 + (sqrt[23]-3)/7
a1 = 1, 7/(sqrt[23]-3) = 7(sqrt[23]+3)/14 = 3 + (sqrt[23]-3)/2
a2 = 3, 2/(sqrt[23]-3) = 2(sqrt[23]+3)/14 = 1 + (sqrt[23]-4)/7
a3 = 1, 7/(sqrt[23]-4) = 7(sqrt[23]+4)/7  = 8 + (sqrt[23]-4)
a4 = 8, 1/(sqrt[23]-4) =  (sqrt[23]+4)/7   = 1 + (sqrt[23]-3)/7
a5 = 1, 7/(sqrt[23]-3) = 7(sqrt[23]+3)/14 = 3 + (sqrt[23]-3)/2
a6 = 3, 2/(sqrt[23]-3) = 2(sqrt[23]+3)/14 = 1 + (sqrt[23]-4)/7
...

Note that each first fraction on the left, when inverted and its floor
value taken, gives the a_i value for the next line. Also, each last
fraction on the right, inverted, begins the equation on the next line.

The puzzle is to evaluate those integers from 2 to 10,000 having
irrational roots and to find the total number of odd periods.
As an example, sqrt[23] has a period of 4, which is even and
does not add to the count. Additionally, one is asked to identify
the longest period present, and the square root that generates it.
(Adapted from Project Euler, problem #64).

There are no comments yet.