Continued fractions

(notes by R. Bigoni)


1. Expansion of a rational number as a continued fraction

A rational number, by definition, is representable by a fraction, ie the quotient between two integers. In fact, the term rational derives from the Latin word ratio, which means quotient.

From each positive fraction Eqn000.gif, reduced to lowest terms, a finite sequence of natural numbers Eqn001.gif can be obtained in the following way

Eqn002.gif

where a0 is the maximum natural number ≤ Eqn000.gif, ie the integer part of the quotient of n divided by d, r0 is the integer remainder of this division and d0 coincides with the denominator d.

For example: Eqn003.gif. In this case a0=2 and r0=3.

If r0 is equal to 0, that is if the numerator is a multiple of the denominator, the procedure terminates. Otherwise, from (1) we have

Eqn004.gif

Obviously d0 is greater than r0, and the fraction Eqn005.gif can be processed like the fraction Eqn000.gif, that is

Eqn006.gif

where a1 is the integer quotient of d0 divided by r0 and r1 the remainder of this division. From (2) and (3) we get

Eqn007.gif

In the above example, we have

Eqn008.gif

Again, if r1 is equal to 0, the procedure ends. Otherwise, from (4) we obtain

Eqn009.gif

Similarly to the previous cases, Eqn010.gif can be written as

Eqn011.gif

where a2 is the integer quotient of r0 divide by r1 and r2 the remainder of this division.

From (5) and (6) we get

Eqn012.gif

In the above example, we have

Eqn013.gif

In this example we can see that r2, the last obtained remainder, is equal to 1. When the remainder is 1, the next remainder obviously will be 0, so we can stop the procedure assuming the previous remainder as last term an of the sequence . In the example we havea3=2. As long as the rest is other than 1, the procedure must be repeated.

In the example, we have seen that from the fraction Eqn014.gif we get the sequence [2;1,1,2]. This sequence is said the continued fraction expansion of the fraction Eqn014.gif.

The elements of the continued fraction expansion can be quickly obtained from the euclidean algorithm to calculate the greatest common divisor of two natural numbers, recording at each step the successive quotients, while the remainder is greater than 0.

Euclidean algorithm: example 1
13 5 3 2 1
quotient 2 1 1 2
remainder 3 2 1 0

A slightly more complicated example: Eqn015.gif

Euclidean algorithm: example 2
157 2791 157 122 35 17 1
quotient 0 17 1 3 2 17
remainder 157 122 35 17 1 0

Therefore the continued fraction expansion of Eqn015.gif is [0; 17, 1, 3, 2, 17].

This second example shows an interesting property: in the expansion of a fraction less than 1, the first term is 0 and the following terms coincide with those of its reciprocal.

 

Given a continued fraction expansion, the generating fraction can be obtained by reversing the procedure previously exposed: we must calculate the reciprocal of the last term of the expansion and add it to the previous term; next we calculate the reciprocal one of this sum and add it to the previous term and so on until the first term is reached. Taking the first example above, we have:

With the second example, we have:


2. Calculator.

The following JavaScript application may be useful to calculate the continued fraction expansion and to do the reverse operation. The button to continued expands a number, written either as fraction or as decimal number. The button from continued performs the inverse operation. The field decimals allows you to set the maximum number of elements of the expansion.

Examples.

 

 


3. Expansion of an irrational number as a continued fraction.

An irrational number, by definition, can not be represented by the ratio between two integers, then we can not apply the Euclidean algorithm to an irrational number to obtain its expansion as finite continued fraction, for the same reason, for which we can not obtain a finite representation of the number whichever is the basis adopted. It is known that the decimal representation of an irrational number is a non-repeating decimal number, but, if we wanted to represent it in base two, we would obtain a non-repeating binary number, or, if we wanted to represent it in base sixteen, we would obtain a non-repeating hexadecimal number. However, at least in some cases, is quite simple, using a procedure analogous to that used for the rational numbers, deduce its expansion as infinite continued fraction.

Let us consider, for example, the square root of two, which was the first irrational number discovered in the history of Western mathematics within the Pythagorean school. We have

Eqn025.gif

So

Eqn026.gif

If we recursively apply this identity to the roots of two within the denominators, we get

Eqn027.gif

Obviously this recursive procedure can always be repeated, so the procedure does not end, but it is not hazardous to say that the continued fraction expansion of the square root of two is

Eqn028.gif

The square root of 2, which, when represented in base ten, is a non-repeating decimal, when developed as a continued fraction has an infinite repeating expansion.

Another very interesting example is given by the golden number Φ. We have

Eqn029.gif

Then

Eqn030.gif

If we recursively apply this identity to the numbers Φ within the denominators, we get

Eqn031.gif

Therefore the expansion of Φ as a continued fraction is

Eqn032.gif

 

In general, for any real number x:

Eqn033.gif

where [x] is the maximum integer number ≤ x, that is its integer part, and {x} = x-[x] is its fractional part. If the fractional part is greater than 0, the reciprocal Eqn034.gif is a real number greater than 0 that, at its turn, can be expressed as the sum of its integer and fractional parts.

Eqn035.gif

If we represent by xi+1 the reciprocal of the fractional part of xi, we can endlessly repeat this procedure and obtain, at every step, a new term of the infinite sequence of the integer parts of the numbers xi; so the expansion of x as a continued fraction is

Eqn036.gif

If you want to use the calculator in section2 to obtain the continued fraction expansion of the square root of 2, it makes no sense to write as input a decimal approximation to it, for example 1.41421356, because you would get the expansion of a rational number that would be finished. You can, in this and similar cases, use the selector functions that brings into input one of the names of the most used real variable functions. You can also use the selector constants, that brings into input one of some of the best known real constants such as e, π and Φ.

Examples.

The same results can be obtained with Mathematica, if you have installed this software, or free with WolframAlpha (documentation), which allows you to use some features of Mathematica.

 


3. Periodic continued fractions.

In general, the expansion of an irrational number as a continued fraction is a good way to obtain a rational approximation to the number itself. For example, the number Φ, which can be approximated by the quotient between a number of the Fibonacci sequence and the previous one, with better approximations as we go on the Fibonacci sequence, can also be approximated at will from its continued fraction expansion, consisting of an infinite sequence of 1. We can also take this fact to define Φ: it is the number represented by Eqn037.gif, where the line over the second 1 indicates its periodicity.

The same applies to Eqn038.gif.

In general, the square roots of natural numbers have periodic expansions.

This is quite easy to prove if the radicand is the number immediately following a square. In fact

Eqn039.gif

then

Eqn040.gif

By recursively applying the identity (10), we obtain

Eqn041.gif

In conclusion

Eqn042.gif

From (11)

 

If the radicand exceeds the square of a natural number of 2 units, we obtain

Eqn046.gif

then

Eqn047.gif

By recursively applying this identity, we obtain

Eqn048.gif

The last obtained denominator coincides with that of the first line, so the cycle repeats regularly. In conclusion

Eqn049.gif

From (13)

Conversely, a repeating continued fraction can be expressed by the solution of a quadratic equation with natural coefficients.
Example: a fraction with two repeating digits.

Eqn100.gif

The number x is given by the positive solution of the equation

Eqn101.gif

From (14) we obtain particularly simple cases for c=2a and multiple of b. Examples:

 


4. Regular continued fractions.

From (9), if we assume x=cotanh(1) and use a calculator, we get

Eqn054.gif

Eqn055.gif

Eqn056.gif

Eqn057.gif

If you use the calculator in paragraph 2, you get get

fig06.gif

Obviously, the continued fraction expansion of cotanh(1) is not periodic, but it shows a remarkable regularity: we can conjecture that it is given by the sequence of the odd numbers.

Eqn058.gif

In fact, the conjecture is correct, and has been demonstrated by Euler.

The base e of the natural exponential, ie the Euler'number.

fig07.gif

Also in this case we can note a clear regularity: from the third term forward, we see the even numbers followed by a pair of 1. We may conjecture that the continued fraction expansion of e is

Eqn059.gif

If we suitably extend this sequence and calculate the generating fraction, we can approximate e with the desired precision. This method of approximation can be a viable alternative to the Maclaurin series expansion.


To learn more...


last revision: June 2016