Just last month we were looking at fractions, which I described as a particularly barren part of the mathematical landscape. Every spot has some redeeming features, however, and I pointed out “Egyptian fractions” as a site of local interest and beauty.

The Egyptians of the middle kingdom (the times of the most famous pharaohs) used only reciprocal fractions – those with “one” as the numerator – and found this to be no drawback at all. For our part, calculating with reciprocal fractions turns out to be refreshing and challenging. Together we discovered Fibonacci’s Greedy Algorithm that turned any known quantity into a series of different reciprocals, and we observed a rule for turning a fraction like (2/n) into a pair of different reciprocals.

As an example, application of the Greedy Algorithm turns (5/19) into:

(1/4) + (1/76).

The “numerator two” rule turns (2/19) into:

(1/20) + (1/380).

By combining these rules you can get some interesting results: you can apply either rule to a number (2/n) so, Fibonacci gives us another pair of reciprocals for (2/19):

(1/10) + (1/95).

So now we have four different reciprocals that add to (4/19).

As a challenge (in last month's column) I left you with the problem to find five different reciprocals that add to (1/3). There are actually several different answers possible, depending on what manipulations of these formulae you use. One trick would be to change (1/3) to (2/6). When you use the second rule you will end up with non-integers:

(1/3.5) + (1/21).

You can instantly convert the first of these to (2/7) and then applying the same rule again to this, you get:

(1/4) + (1/28).

Gathering these, we have:

(1/3) = (1/4) + (1/21) + (1/28).

By the Greedy Algorithm we also have:

(1/3) = (1/4) + (1/12), and so we can add these two groups together:

(2/3) = (1/2) + (1/12) + (1/21) + (1/28).

Divide both sides by two and we get:

(1/3) = (1/4) + (1/24) + (1/42) + (1/56)

We can carve up any one of these four reciprocals to form two others, using the Greedy Algorithm yet again:

(1/4) = (1/5) + (1/20)

Now we can substitute these two reciprocals into the earlier set of four, and we get five summing to (1/3):

(1/5) + (1/20) + (1/24) + (1/42) + (1/56)

This is only one possible answer.

Continuing with Fractions

When the Egyptians wanted to deal with a fraction, they looked for the nearest reciprocal that was less than the value, and then continued this process with the leftovers. Another way forward would be to insist on making a single reciprocal fraction. Four fifths, for example, can be expressed as the reciprocal 1/(5/4). This is great, except that the denominator 5/4 is no integer: it is itself an “improper fraction”, one plus a fraction. That new fraction is 1/4, which (fortunately) is a reciprocal. So four fifths is:

1/(1 + 1/4).

We have converted our original number into the form (x + 1/r) where r is in the same form, but with its own x and r. At the first level, x is 0 and r is 5/4. At the next level x is 1 and r is 4. Finally there is a third level, where x is 4 and r is zero. In this little algorithm r eventually becomes zero, so no more reciprocals can be formed. On the way, we have x become 0, 1 and 4. If you think about it carefully, you will see that this is just another variant of Euclid’s ubiquitous algorithm for finding the “highest common factor” of two integers. Fractions in this form are called “continued fractions”, or sometimes “chain fractions”. The “x” parts are the most important – all the rest is just window dressing, the same for every continued fraction. A continued fraction is represented symbolically with parentheses enclosing all the “x” parts, separated by commas. In this instance we have established that 4/5 = (0, 1, 4).

Let’s take another example: a little more complicated. 0.2973 can be converted to continued fraction form by converting it first to a reciprocal (that is, a fraction with “1” as its numerator). As a vulgar fraction it is 2973/10000, and as a reciprocal it is 1/(10000/2973). Carrying out the division this is 1(3 + 1081/2973), and we have forged the first two links in the chain: (0, 3..). We continue by making 1081/2973 into a reciprocal. With a bit of persistence we will end up with the chain: (0, 3, 2. 1, 3, 270). The last fraction we get is 1/270 which is already a true reciprocal. It becomes our last “x”.

The chain (0, 3, 2, 1, 3, 270) has exactly the same value as 0.2973, and we can convert freely between these two forms. To convert from the chain back to the decimal, you must start at the right end and move leftward:

3 + 1/270 = 811/270

1 + 270/811 = 1081/811

2 + 811/1081 = 2973/1081

3 + 1081/2973 = 10000/2973

0 + 2973/10000 = 0.2973

I’m afraid that the final 270 in the chain looks a bit out of place: so much larger than the others in the chain. I wonder what happens when we drop it from the chain and re-evaluate?

1 + 1/3 = 4/3

2 + 3/4 = 11/4

3 + 4/11 = 37/11

0 + 11/37 = 0.297297..

It comes out at very nearly the same overall value: we can conclude that the final 270 link in the chain is of very small significance. In fact, the larger the link is, the less its significance. What about dropping another item from the end of the chain? When we expand it again..

2 + 1/1 = 3

3 + 1/3 = 10/3

0 + 3/10 = 0.3

Still close, but we have lost quite a bit: the chain (0, 3, 2, 1) has a value of 0.3. Lop off another link in the chain and you will find that (0, 3, 2) has a value of 0.285714.. The chain (0, 3) is equivalent to 0.333.. Note that shorter chains produce at least a near miss: a two-link chain (0, 3) is too high: the three-link chain (0, 3, 2) is too low, but nearer. Four links (0, 3, 2, 1) is too high, but even nearer. The five-link chain (0, 3, 2, 1, 3) is low, but extremely close. Absolute precision in this case requires six links. This behaviour is characteristic of all chain fractions, no matter how many numbers end up in the chain. If you think of shortened chains as estimates, the longer the chain, the better the estimate: consecutive estimates (lengthening the chain by one link each time) home in on the exact value, alternating between low and high estimates.

For example let’s try an interesting decimal fraction: 3.14159265. This is PI to eight decimal places. (PI has no end to its decimal, but stick with me for the time being: eight places is good enough for everyday use). Go through the steps and you will build a string that runs (3,7,15,1,288..). There is a tiny fraction still left after generating the 288, but it is so insignificant we can stop there for now. If you go through the trouble of evaluating that chain as described, you will confirm that it does, indeed, come out to 3.14159265. What if we shorten it and re-evaluate? (3,7,15,1) actually comes out to 3.14159292, so it is good enough as an approximation of PI to five decimal places. The shorter chain (3,7,15) comes to 3.14150943, which is less accurate an approximation, but not too bad. Even the tiny chain (3,7) isn’t a mile off: it expands to 3.14285714.

Of course we don’t have to work out the decimal equivalent of a particular chain fraction. If we just convert a chain back to an ordinary fraction, interesting things develop. Take (3,7,15): This actually means (3 + 1/(7 + 1/15)). First off, we must calculate (7 + 1/15) as a single fraction, (106/15). Placing that back in the original gives us (3 + 1/(106/15)), or (3 + 15/106), which we get by “unreciprocating” the reciprocal. Then (3 + 15/106) becomes (333/106). Now think through this carefully: this means that (333/106) is an approximation of PI, admittedly not as good as if we had evaluated a chain of four or more items, but still a fair approximation. What if we start with a chain only two items long? That’s (3,7) – and when we work that out, we get 22/7. You have most likely seen this approximation before: it is rough, but easier to use than a long decimal fraction – at least if you are calculating without a computer.

The more terms in a continued fraction, the greater the accuracy of the approximation it is making.
Note that corrections alternate between positive and negative, and the magnitude of error decreases dramatically.

Though 333/106 turns out to be a good approximation for PI, 355/113 is far better: this is the value of (3,7,15,1), the fourth approximation. Sixth century Chinese mathematician Tsu Chung Chi used this as a handy approximation of PI, but he spent weeks testing different fractions to find it; you have found it the easy way, with just one chain fraction. The Just BASIC source of a program called ChainFractions.bas is available here for download. You can obtain Just BASIC, entirely without charge, at www.justbasic.com.

This little program calculates a chain for a decimal number you provide at run-time. It limits itself to dealing with eight decimal places, but that is arbitrary: the same method can create chains for numbers of any length.

It prints on the screen each of the partial chains on the way to the full result, including their fractional form and the error in approximation. Experiment with it, generating continued fractions for various decimals, and note the fractions generated as approximations on the way. Two numbers of interest to try are the mathematical constants epsilon (about 1.71828183) and phi, the “golden mean” (about 1.6108034). Think about occasions when a good fractional approximation may be more desirable than a decimal expression – they occasionally crop up! And fractions made up of a couple of three or four-digit numbers are more easily memorised than decimal constants with eight digits of precision.

A section of output from the program ChainFractions.bas, showing shorter chains and less precise approximations on the way to the generation of the full chain.

Another Application

One particular field in mathematics has been very fruitful in the last century, though it has been a favourite study of many over the years: Diophantine Analysis. More broadly, it involves “number theory”, and deals with whole numbers as if fractions and surds (like the square root of 2) do not deserve attention. For example an expression like (5x - 13y = 1) means one thing to an algebraist, but to a number theorist it is another matter. The algebra user sees this as a straight line on a graph: any point along that line provides a different x,y pair that fits – in fact, an infinity of pairs. A number theorist will be looking only for whole numbers as x and y – and unless you specify otherwise, he will look only for positive whole numbers. To him there are an infinity of solutions, but they all feature whole numbers for both x and y. Examples are: (8,3), (21,8), (47,18).

Once you have found one solution, all the others are at hand: you just add or subtract 13 repeatedly from the x value, and add or subtract 5 the same number of times from the y value. The pair (8,3) works, so (8+13n, 3+5n) is a template for all other solutions. But how do we get (8,3)? Trial and error may be fine for small equations, but not for bigger ones, surely!

It is to me a dazzling fact that chain fractions provide a solution! The starting-off value for (x,y) in (5x-13y=1) can be established by building the chain fraction for (13/5), and then lopping off the very last term in the chain!

Let’s try it out for size: (13/5) becomes the chain fraction (2,1,1,1,1). Now we lop off the final term to get (2,1,1,1), and change this back into a fraction. (2,1,1,1) = 8/3, and the 8 becomes the jumping-off value for x, and the 3 for y. This little miracle doesn’t stop there: different things happen if you want to solve an equation like 5x + 13y = 492 in whole numbers. It is different because it is addition, and the result is not just “1”, but the calculations for all these equation forms start off with converting the 5 and 13 into a chain fraction. The extra work is brief, but requires only multiplication and knowledge of “modulo” arithmetic. Modulo arithmetic (or “clock numbers”) is itself a completely enjoyable operation to my way of thinking -- division without decimals! We will have to look at this at another time.

Look at decimals for another few moments, and consider the different types.

• “finite” decimals: they go on so far, and then end: example .0016285
• “repeated” decimals: they don’t stop, but they “end” with a single digit repeated, or a group of digits repeated: .898348983489834…
• “endless” decimals: they go on forever (so far as we know) but there is no sign of repetitions: 3.1415926535..

The first two types are similar: they are both “Rational”, which means that they represent fractions: one integer (however long) divided by another. Ironically the third type consists of two types of numbers: “surds” and “incommensurables”. Surd describes any quantity involving a “fractional power”. This means things like the square root or cube root of a number which is itself not rational. The square root of .0625 is rational (it is .25), but the square root of 26 is irrational, which is incommensurable. PI is irrational, incommensurable, and also “transcendental” – another characteristic type that means it cannot be defined by any equation that manipulates rationals or surds.

Note that you can look at a decimal, and if it either ends or has a repetitive tail, you know it is rational, and can be represented by a fraction. What about a chain fraction: can you tell anything from observing its numbers? The answer is surprising to say the least: if the chain ends, its value is rational, but if it has a repeated tail, its value is a surd! For example the square root of 13 is (3,1,1,1,1,6,1,1,1,1,6,1,1..) the tail made up of 1,1,1,1,6 repeated endlessly. How do you convert a surd to its chain fraction form? Well, that’s an interesting little task involving an algorithm too long to include this time. Maybe this bit of mathematical landscape is worth another visit some day.

Several different ways to represent the same value: first as a decimal fraction; next as a chain (or “continued”) fraction in long form and in compact notation; finally as a decimal “approximation” evaluated from the chain.

March 2006