Continued fractions

Mark C. Chu-Carroll from Good Math Bad Math has a nice explanation of continued fractions, what they are and why they are useful.

I like continued fractions. They're neat and full of wonderful properties. They are the basis of a lovely little algorithm for converting arbitrary decimal numbers into fractions. There are some great patterns in continued fractions too, like the square root of two. sqrt(2) can't be written exactly as a simple fraction, and the decimal expansion is messy: 1.414213... it goes on for ever, and despite the first couple of 14s there's no pattern to it.

But write it as a continued fraction and you'll see a wonderful pattern:

1 + 1/(2+ 1/(2+ 1/(2 + 1/(2 + ... )))

which can be written as [1; 2, 2, 2, 2, ...].

You want the reciprocal of sqrt(2)? That's easy: [0; 1, 2, 2, 2, 2, ...]. Or, expanding it:

0 + 1/(1 + 1/(2+ 1/(2+ 1/(2 + 1/(2 + ... )))

The rule for forming the reciprocal of a continued fraction is simple. If the whole number part (the first number, before the semicolon) is 0, you remove it and shift all the numbers one to the left. If it isn't zero, you shift all the numbers to the right by one, and stick a 0 as the whole number part.