Continued fractions of square roots

Let’s look at the continued fraction representation for √14.

sqrt{14} = 3 + cfrac{1}{1+ cfrac{1}{2+ cfrac{1}{1+ cfrac{1}{6+ cfrac{1}{1+ cfrac{1}{2+ cfrac{1}{1+ cfrac{1}{6+ ddots}}}}}}}}

If we were to take more terms, the sequence of denominators would repeat:

1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, …

We could confirm this with Mathematica:

    
    In:  ContinuedFraction[Sqrt[14], 13]
    Out: {3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6}

For any integer d that is not a perfect square, the continued fraction for √d has a pattern that we see above.

  1. The coefficients after the first one are periodic.
  2. The cycle consists of a palindrome followed by a single number.
  3. The last number in the cycle is twice the leading coefficient.

In the example above, the periodic part is {1, 2, 1, 6}. The palindrome is {1, 2, 1} and 6 is twice the initial coefficient 3.

Another way to state the third point above is to say that the leading coefficient is the integer part of the square root of d, i.e. ⌊√d⌋, and the last coefficient in each period is 2⌊√d⌋.

Annotated version of continued fraction for sqrt(14)

Sometimes the palindrome is empty:

    In:  ContinuedFraction[Sqrt[5], 10]
    Out: {2, 4, 4, 4, 4, 4, 4, 4, 4, 4}

In the continued fraction for √5 the palindrome part is empty and we repeat 4, twice the initial coefficient.

For √3, the palindrome is simply {1} and the final number is 2.

    In:  ContinuedFraction[Sqrt[3], 13]
    Out: {1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}

One last example:

    In:  ContinuedFraction[Sqrt[71], 17]
    Out: {8, 2, 2, 1, 7, 1, 2, 2, 16, 2, 2, 1, 7, 1, 2, 2, 16}

More continued fractions posts


Leave a Reply

Your email address will not be published. Required fields are marked *

*

Categories

Top