Euclid and continued fractions

13 years ago

Back in my days at Kings College, there was a movement to try and make sure that we mathematics students could write. There was a general worry that because we expressed ourselves tersely and symbolically in the language of mathematics we would forget how to express ourselves correctly in the language of English. So, while I was there, we had to write two essays, one at the end of our first year and one at the end of the second. The essays should be on a mathematical subject, maybe even with a proof or two, but it had to be preponderantly a narrative. (If you think about it, this is the same worry that developers might not be able to express themselves clearly and concisely to their users, which is why there’s so much emphasis on “written and verbal communication” in job descriptions.)

My first essay was on the Prime Number Theorem – if  π(n) is the number of prime numbers less than n, then the following holds:

or, if you like, you can approximate the number of prime numbers less than n by using n / ln(n).

My second essay was on continued fractions, and for the life of me I can’t remember what I wrote about at this remove. I think I have the first essay downstairs in the basement somewhere (I got an A for it), but the second has been lost – or maybe I deliberately left it somewhere (I got a B-, I think).

Back in Victorian times (and earlier) continued fractions were a hive of research, but in the 20th century mathematicians moved on from them and they’re somewhat old-fashioned nowadays. Nevertheless they are very interesting, if peculiar.

First of all, here’s a simple (finite) continued fraction:

If you feel up to it, you can easily show that this is equal to 355/113, which is a pretty good approximation to π. In essence: all the numerators in a continued fraction should be 1, and it’s the denominators that are the important bits.

Since writing continued fractions gets pretty tedious (I’m using Word’s Equation editor for these), there’s a simplified form that takes up much less space: just list the denominators separated by commas, with the integer part delimited by a semi colon. Here’s our continued fraction for 355/113: [3; 7, 16]. Sequence A001203 in the Online Encyclopedia of Integer Sequences is this continued fraction for π and gives us [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, ...]. Like its decimal representation, the continued fraction for π is infinitely long and has no pattern to the denominators. (Note, in case you were wondering: if you chopped off the sequence just before the 292 denominator and wrote out the continued fraction, you’d get:

Which evaluates to the same as before.)

Anyway, back to continued fractions and Euclid. Way back in ancient Greece, Euclid described an algorithm for calculating the greatest common divisor (GCD) of two integers (he actually described it in geometric terms, but the principle still applies). The GCD is the largest number that divides both numbers without any remainder. The Euclidean algorithm goes like this: we divide the smaller number into the larger and take the remainder. For the next time round, the previous smaller number becomes the larger and the remainder becomes the smaller. Using our example of 355 and 113:

GCD(355, 113) = GCD(113, 16), since 355 = 3 × 113 + 16
              = GCD(16, 1), since 113 = 7 × 16 + 1
              = GCD(1, 0), since 16 = 16 × 1 + 0

As we now have a remainder of 0, we stop the process: the new larger number is the GCD of the two original numbers (in our case, it’s 1).

But notice something interesting: the multiplicative factors (handily shown in red) are the denominators of the continued fraction. So 355/113 = [3; 7, 16]. 

Let’s try it with 348 and 204:

GCD(348, 204) = GCD(204, 144), since 348 = 1 × 204 + 144
              = GCD(144, 60), since 204 = 1 × 144 + 60
              = GCD(60, 24), since 144 = 2 × 60 + 24
              = GCD(24, 12), since 60 = 2 × 24 + 12
              = GCD(12, 0), since 24 = 2 × 12 + 0

So, the GCD is 12, and the continued fraction is [1; 1, 2, 2, 2] or fully spelt out:

In fact, the Euclidean algorithm guarantees that any fraction a/b (a rational number) will have a finite continued fraction.