Let’s look at the continued fraction representation for √14.
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.
- The coefficients after the first one are periodic.
- The cycle consists of a palindrome followed by a single number.
- 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⌋.
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}
This is a very cool fact I hadn’t run into (or if I had, hadn’t realized the significance).
Would you mind updating the post with some reference links? I’d expect there to be proofs of these cool facts.
You can find it in a lot of number theory books. For example, it’s in the textbook I had long ago, The Theory of Numbers by Niven and Zuckerman. However, the theorem stated there doesn’t include the part about the coefficients forming a palindrome.
I’ve seen a reference saying there’s a proof in the book Continued Fractions by Carl Douglas Olds, but I don’t have the book and it’s out of print.
Thanks. Olds’ book sounds like one I’d like to track down.
Professionally, I’m a developer and IT consultant (ThoughtWorks). On a side project, I’ve noodled at “big rational” (unlimited precision, barring memory limits) representations for the JVM (Kotlin), and a piece of that project is conversion to/from finite continued fractions. It’s an area which fascinates.
Thank you again for the post!
When I first saw continued fractions, I thought they were a typographical novelty, recreational mathematics. They would still be interesting if that were the case, but they’re also practical. Numerical libraries use them, for example, to compute special functions.
I’ve played around with continued fractions, and used them professionally, but I don’t feel like I understand them nearly the way I understand, say, power series. They’re still mysterious.
Brian, I found another reference on the theorem, this one including the palindrome part.
Samuel S. Wagstaff, Jr. The Joy of Factoring. Theorem 6.13.