#continued fraction

[mathhombre]

Square Root Continued Fraction

via Archimedes Lab on FB. Particularly nice for root 2 and root 3.

[carotjuice]

[wiskwa-en]

Euclid’s algorithm

This is a translation of an appendix of an article that appeared in the April 2004 issue of Pythagoras.

We desribe Euclid’s algorithm for finding the largest common divisor of two natural number and indicate how it can be used to find continued fractions for irrational numbers.

In Euclid’s Elements you will find, in Book X, the following proposition If, when the less of two unequal magnitudes is continually subtracted in turn from the greater that which is left never measures the one before it, then the two magnitudes are incommensurable.

This sounds a bit strange maybe but you should read it geometrically. Euclid worked with line segments, as many units long as the numbers you work with are large. In this context `measuring’ means that the smaller segment goes a whole number of times into the larger one, that is, the smaller number divides the larger one. Also: `incommensurable’ means that only the unit length goes a whole number of times into but and that means that the numbers are relatively prime, that is, their largest common divisor is equal to 1.

Take, for example, 8 and 3. Subtract 3 from 8, we get 5, that is larger than 5, so subtract 3 again, with 2 as the result. Now 3 is the larger, so we subtract 2, and 1 is left. At no time did we have a remainder that was a divisor of the previous number until we reached 1 (the unit). Conclusion: 8 and 3 are relatively prime.

Immediately after that Euclid used the proof to find the largest common divisor of two numbers: To find the greatest common measure of two given commensurable magnitudes. he noted that at the moment when it does happen that `which is left measures the one before it’ we have found the largest common divisor.

The largest common divisor (lcd) is what the name says: a divisor of both numbers and the largest among these. Euclid’s algorithm gives an efficient way to find that largest common divisor, for example lcd(54,20).

Subtract 20 from 54, twice, with rest 14. The rest does not divide 20, we continue: subtract 14 from 20, with rest 6; because 6 does not divide 14 we perform another step: subtract 6 twice from 14, with rest 2. Because 2 is a divisor of 6 we have found the largest common divisor of 54 and 20: lcd(54,20)=2.

You can look at the algorithm from a geometric viewpoint. To find lcd(8,3) take a rectangle of 8 by 3. For lcd(54,20) use one of 54 by 20. In both cases try to tile the rectangle with squares; the side of the largest usable square is the lcd of the sides of the rectangle. That largest tile you find by taking away squares until a square remains; this is in fact what the algorithm says we should do. The last picture below shows that lcd(8,3)=1.

Take a large sheet of graph paper and draw a rectangle of 54 by 20. Then perform this version of Euclid’s and in the end you will find a 2 by 2 square.

Nowadays Euclid’s algorithm is described as follows: “keep dividing the larger by the smaller until the division has remainder 0”, when that happens you will have reached the largest common divisor. We use Euler’s number from the first part once more:

When the division finally works out the `smaller’ is equal to 1, so lcd(1461,59)=1.

You can perform Euclid’s algorithm with any two numbers. If x is an irrational number then applying the algorithm to x and 1 will yield the numbers in the continued fraction for x. When you subtract 1 from √2 then the rest is equal to √2-1. But if you then subtract √2-1 from 1 (twice) then something nice happens:

You could have seen this coming: √2-1 is a solution of x2+2x-1=0. The pattern keeps repeating:

and in general

The first result can also be written as

or as

And this leads to the continued fraction that Euler found for √2 or rather for √2-1:

In theory this can be done for every irrational number in the interval (0,1). Sometimes, as Euler did in the case of (e-1)/2, you find a nice regular sequence of natural numbers to describe that particular irrational number. The wikipedia page on continued fractions is a good place to start exploring.

[wiskwa-en]

Euler and the number e

This is part one of a translation of an article that appeared in the April 2004 issue of Pythagoras.

Leonhard Euler was a master of manipulating infinite sums, products, and fractions. We shall see how he found an expression for the nummber e.

Leonhard Euler was a master of manipulating infinite sums, products, and fractions. We shall see how he dealt with exponential functions.

In 1755 Leonhard Euler wrote a book titled Introduction in Analysin Infinitorum (Introduction to the Analysis of the Infinite). In this textbook Euler treated "the theory of functions of variable quantities, their factorizations and developments into series; also the theory of logarithms, circular arcs and their sines and tangents, and many other things that are of importance for the Analysis of the Infinite".

Continued fractions

We have seen continue fractions before but Euler was one of the first to study them systematically. He devoted the last chapter of his book to them. Continued fractions appear when you apply Euclid's algorithm to pairs of numbers in order to find their largest common divisor.

Euler's first example was the fraction 1461/59. Euclid's algorithm repeatedly performs divisions ans remembers quotients and remainders. In our example the first step yields 1461=24×59+45, or 1461/59=24+45/59. Next we turn the remainder upside down and find 59/45=1+14/45 and so

In the next step we get 45/14=3+3/14, so that

If we keep going we find 14/3=4+2/3, 3/2=1+1/2 and 2/1=2+0. We plug all this into the fraction:

Such a compound fraction is called a continued fraction. For normal fractions this leads to seemingly more complicated expressions but you should realize that there is a trade-off: the numbers that occurs in the continued fraction — 24, 1, 3, 4, 1, 2 — are quite small compared to 1461 and 59 and that can be an advantage when storing the number.

For numbers that can not be written as fractions, like &radic2;, π and e you can use continued fractions to make very good approximations in a very efficient way. For √2 Euler gave the following expression

Exercise Expand the first few partial fractions — 1, 1+1/2, 1+1/(1+1/2), … — and compare them with √2.

A formula for e

It is said that Euler calculated like other people breathe. Through all those calculations he discovered connections that other people just did not see. He found a continued fraction for e, not directly but via the quotient (e-1)/2. He started with the approximation 2.718281828459 of e and turned it into this approximation 0.8591409142295 of (e-1)/2. Then he performed divisions such as those above but now for

That gave the following results

That work lead to this continued fraction:

Euler wrote: "with better approximations of e we would have found the sequence 1, 6, 10, 14, 18, 22, 26, 30, 34, … (with 4k-2 in the kth position, starting from k=2). The partial fractions that you get in this way give very accurate approximations of (e-1)/2 and hence of e itself. Expanding such a continued fraction seems like a lot of work: in the fraction above we start with 18+1/22=397/22, then 14+22/397=5580/397, then 10+397/5580, and so on. That takes some effort and you needs to start all over again with each next partial fraction.

Fortunately there is a relation between the numerators and denominators of the consecutive fractions. The first fraction is 1/1 (do not simplify), the next one is 6/7, the third is 61/71. But now note: 61=1+10×6 and 71=1+10×7. The next fraction is860/1001, and there we have 860=6+14×61 and 1001=7+14×71. The next one is

In general: the fraction that you get when you stop at 4k-2 is made from the previous two fractions p/q and r/s in the following way

If you start the sequence with 0/1 before 1/1 then this formula works for k=2 too.

Exercise To get fractions for e you take those for (e-1)/2 and multiply them by 2 and add 1 to the result. Verify that the resulting fractions can also be obtained by starting with 0/1 and 3/1 and then using the recursive formula for the numerators and denominators.

Next time we shall see how Euler found Newton's formula for the exponential function, in a completely different way.

[wiskwa-en]

Continued fractions for the square root of 13

Yesterday we looked the equation x2-13y2=1 and used the continued fraction of √13 to find solutions. We did not specify how to construct such a representation of √13. For certain numbers you can make them, with a bit of perseverance.

Let us consider √13. The first thing we do is note that 3<√13<4 and work with √13-3 rather than √13. Next we note that (√13-3)(√13+3)=4. We can (re)write this equality as

But then you can replace the √13-3 in the denominator by the whole right-hand side, and again, and again, …, this leads to this continued fraction

That is not yesterday's continued fraction but you can use it too to find approximations of √13. If you add 3 to the convergents of this fraction then you get 11/3, 18/5, 119/33, 393/109, 649/180, …. This is a subsequence of yesterday's approximations. The solutions of x2-13y2=1 and 13y2-x2=1 can also be found in this sequence.

Can we use this to make yesterday's continued fraction? Yes, all you need is pencil and paper and the first fraction, 4/(6+(√13-3)) that is. Divide numerator and denominator by 4; the numerator becomes 1 and the denominator will be 6/4+(√13-3)/4; this you can rewrite to 1+(√13-1)/4. Next: divide the numerator and denominator of (√13-1)/4 by √13-1; we get 1 and 4/(√13-1), respectively. But, as above, we observe that (√13-1)(√13+1)=12 and so 12/(√13-1)=(√13+1), or 4/(√13-1)=(√13+1)/3 which we can turn into 1+(√13-2)/3. The results of these two steps are displayed below:

If you keep doing this you will after two steps more arrive at the fraction on the left below. Now we read our initial equality as (√13-3)/4=1/(6+(√13-3)) and this gives of the fraction below on the right

But now we can replace (√13-3) by that fraction on the right, and again, and again, … and this leads to yesterday's continued fraction.

Exercise Do the same for √2-1 and √3-1 and construct approximations of √2 and √3 in this way, and thus also find solutions to the Pell equations x2-2y2=±1 and x2-3y2=±1.

[wiskwa-en]

Continued fractions and the Pell equation

x^2=ay^2+1 why is the square root of a=13 the fraction 1/(180/649) the value of y and x?

How can it be that apparently in the number a (and several other value of a) the value of x and y is baked in?

To begin: the quotient q=649/180 is not equal to √13 even though the question seems to suggest it is. You can see that because 649 and 180 form a solution to the equation: 6492-13×1802=1. Divide by 1802, we get q2-13=1/1802, so q2 is not equal to 13. However, we can factor the left-hand side of the equality: (q-√13)×(q+√13)=1/1802. Because q>√13>3 we can deduce that q-√132). That is about 0,0000051440 and that may make it seem that 649/180 is equal to √13.

The second part of the question, “Why are x and y baked into a?”, can be answered as follows. The equation in the question, x2=y213+1, is an instance of Pell’s equation. One way to solve this is by looking at the continued fraction of √13 (in general that of a).

You can take partial fractions of this infinite expression by chopping it off just before a plus-sign. In this case that will yield, in order 3, 4, 7/2, 11/3, 18/5, 119/33, 137/38, 256/71 393/109, 649/180 … These fractions provide very good approximations of the value of the full continued fraction, in this case √13. Those partial fractions are called the convergents of the continued fraction.

For us the convergents 18/5 are 649/180, these you get when you cut off just before a 6. At a 6 the fraction starts afresh and you could write 6+(√13-3) rather than the rest of the fraction to get a valid equality If you substitute the numerator for x and the denominator for y in the Pell equation then 18/5 will give 182=52×13-1 and 649/180 gives, as we saw above, 6492=1802×13+1. At the next 6 you get a fraction that gives -1 again and at the 6 after that we get 1, the fraction is 842401/233640 (substitute in the equation: x=842401 and y=233640 form another solution).

The theory of continued fractions tells us that the absolute value of the difference between √13 and a convergent m/n is smaller than 1/n2. If the numerator and denominator are solutions of the Pell equation we can improve this with a factor 1/6.

In general you also get upper bounds like these. From x2-ay2=1 it follows that (x/y)2-a=1/y2 (divide by y2). Factor the left-hand side: (x/y-√a)(x/y+√a)=1/y2. We have x/y>√a; and so x/y-√a2√a). The solutions to the of the Pell equation give very good approximations of √a. `Very good’ because the difference is less than 1/y2, where y is the denominator of the fraction.

The solutions to the `reverse’ Pell equation, ay2-x2=1, also yield very good approximations of √a. The only difference is: the fractions from the normal equation are larger than √a and those from the reverse equation are smaller.

Further reading: Solving the Pell Equation by Hendrik Lenstra.

[curiosamathematica]

The complex Rogers-Ramanujan function R is defined by a continued fraction as follows:

This function is defined over the unit disk in the complex plane; the pictures above are visualizations of the imaginary, real, argument, and absolute values of R(z). More information about Ramanujan's R-function, including various bizarre formulas, can be found here.