Next:Calendar and continued fractionsUp:If Pope Gregory knewPrevious:Very brief history

# Continued fractions

The history of continued fractions can be traced back to an algorithm of Euclid.

Let us recall this algorithm. Suppose we would like to find the greatest common divisor of numbers 75 and 33.

The last non-zero remainder, 3 in our case, is the greatest common divisor of 75 and 33.

There is no evidence though that Greeks knew about the connection between the left column and the right column above. The first continued fraction was used in 1572 by Bombelli to approximate . The first infinite continued fraction appears in 1659 in the work of Lord Brouncker to expand . It is Euler's systematic development of the theory starting in 1737 that showed the value of the notion for both number theory and analysis. A torrent of results followed. In 18th and 19th centuries everybody who was anybody in mathematics contributed.

If the number is rational the continued fraction terminates like for . If the number is irrational the continued fraction goes on forever. For example, for the irrational number  we can execute the Euclidean algorithm, in essence looking for the greatest common divisor of  and . The algorithm will never terminate since the two numbers are incommensurate.

concluding

The esthetic beauty of continued fractions may go some ways towards justifying the significance of some numbers from algebra or geometry. The continued fraction expansion

would suggest that the number  has some significance. In fact, this number is none other than the golden ratio''.

If we terminate the infinite continued fraction for the irrational number  at the th step we will obtain a rational approximation  to . The rational number  is called the th convergent for . For example, the first 4 convergents to numbers  and  are

The name convergent comes from the fact that convergents do converge to the number. For example,

Here is the graph for .

We see that convergents alternately lie above and below the exact value of .

Here is the graph for .

We see the same alternating pattern of approximation. In fact, this is true in general for any number.

The speed of convergence of continued fractions to a number they represent varies from number to number (but it is always very very fast). Here is a comparison between the convergence errors for  (blue) and  (red).

The continued fraction expansions have many remarkable properties. We will be interested mainly in its approximating power relevant for the design of a good calendar system. It turns out that the convergents for the irrational number  have superior approximating properties. The following definition makes it precise what we mean by a good approximation.

Definition 1   The fraction is called a good approximation for  if for any  and any integer  we have .

The good approximations occur when q=2, 5, 12 and 29. The next good approximation occurs when q=70.
The good approximations occur at q=7, 106 and 113. The next good approximation does not occur before q=33,102.

Observe that the numbers  are exactly the denominators in the convergents for  and  respectively. This is not an accident and holds in general for all convergents and for all numbers . We state it precisely and unambiguously in the form of a Theorem.

THEOREM 1   Every convergent  is a good approximation (in the sense of Definition 1) for and conversely, every good approximation to  is one of the numbers  for some . In fact  is the smallest integer  such that  for some integer . We also have the inequalities

The proof of the theorem is given in the book of Serge Lang. It is not very difficult to follow Lang's proof but quite tricky to discover it on your own. Christian Huygens was the first to describe the sense in which coninued fractions give the best approximations of real numbers.

Now that you know that continued fractions are very good at approximating numbers rational and irrational, it is not surprising to find them in many unusual (at first glance) places. Looking deeper at continued fractions you would discover many amazing properties of these objects. We can say that there is music in continued fractions. But also there are continued fractions in music. Armed with continued fractions we return to the calendar and discover how continued fractions can explain more or less any calendar system ever proposed or implemented.

Next:Calendar and continued fractionsUp:If Pope Gregory knewPrevious:Very brief history
Yury Grabovsky

2000-03-03