• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

Continued Fractions

There are several different ways one can express a particular value. We can write the value using different bases, for example. If the value is rational, we could of course express it as a fraction. We can also express rational values as decimal values with digits that either terminate or repeat. The notion of continued fractions gives us yet another alternative to throw into the mix...

We say that a value $x$ has been expressed as a simple continued fraction when it is written in the following form:

where $a_0$ is an integer (possibly zero or negative), and $a_1, a_2, a_3, \ldots$ are positive integers.

As the above is somewhat cumbersome to write and/or type, we often abbreviate this with the following notation:

Converting Rational Values to Continued Fractions

The process for converting an arbitrary rational value into its continued fraction form is straight-forward, and we describe it by example:

Suppose we wish to find the continued fraction form of

Any fraction may be written as the sum of an integer and a positive fraction less than one in magnitude; finding the same here yields.

Now, let us modify the form (but not the value) of the fractional piece using reciprocation:

In doing so, we create an improper fraction in the denominator, which again can be resolved into the sum of an integer and a positive fraction less than one. Note also, that the integer part must be positive, since our improper fraction was positive.

Play the same game again -- reciprocating our fraction less than one, we arrive at

and writing the resulting improper fraction as a sum of an integer and a positive fraction less than one, we get

In this example, we can do this one more time before the process naturally terminates

The above work then tells us that $-95/82 = [-2;1,5,3,4]$.

Finite Simple Continued Fractions

In the case when the sequence of $a_n$ terms terminates (like the one just shown), we say that $x$ can be written as a finite simple continued fraction.

It should be clear that every finite simple continued fraction is rational, as its layers can be collapsed until all that is left is a single quotient of two integers.

For example, suppose we wished to collapse in this way the finite simple continued fraction $[3;2,5,4,2]$.

Starting with the bottom-most layer, we find common denominators to combine the integer and fraction located there, and then we reciprocate the result to eliminate that layer. Then, we do the same thing again, and again -- repeating this process until we have collapsed the entire fraction:

So we know that every finite simple continued fraction is rational -- but is the reverse true? Does every rational value have a finite simple continued fraction form?

Think back to the process we used to turn an arbitrary fraction into a continued fraction. Does this process necessarily terminate in finitely many steps, regardless of our starting fraction?

Yes -- it must!

Arguing by example, consider again the steps seen in turning $-95/82$ into a continued fraction:

Notice the bottom-most fraction at each stage. Each of these, by construction, must be proper fraction (i.e., less than one), so their denominators are always greater than their numerators. So we see that

Again, by construction, the numerator of the bottom-most fraction in any one stage is the denominator of the bottom-most fraction in the next stage, allowing us to create a string inequality

With the possible exception of the very first integer, the construction forces all of the other integers found (denominators included) to be positive. This, combined with the string inequality above, tells us that the sequence of bottom-most denominators must be a decreasing sequence of positive integers. Such a sequence must terminate -- as otherwise it will eventually pass zero and start to produce negative terms (a contradiction).

We have thus shown that not only is every finite simple continued fraction rational, but every rational value can be expressed as a finite simple continued fraction.

Infinite Continued Fractions

How might we construct a continued fraction for an irrational value? Note, we expect such a continued fraction will not have a finite form...

Suppose we wished to do this for $\sqrt{7}$. We can proceed in a very similar manner to what was described to convert a rational to continued fraction form:

Since $\sqrt{7} \doteq 2.645751311\ldots$, we first split it into an integer and a positive decimal value less than one.

Reciprocating the decimal piece, we have

The reciprocation produces something bigger than one in the denominator, which we can again split into an in integer and a positive decimal value less than one.

Again, we follow this with reciprocation...

and so on, producing

At this point, something interesting happens. Notice that the decimal value seen in the last step agrees with the decimal value we saw in the first step. Not surprisingly, our calculations start to repeat themselves from this point forward.

This results in an infinite simple continued fraction representation for $\sqrt{7}$, given by

Borrowing the notation for specifying a repeating pattern in a decimal expansion by placing a bar over the part that repeats, we indicate the periodic nature of this infinite continued fraction by writing