Continued Fraction

A continued fraction writes a number as an integer plus a fraction whose denominator is itself an integer plus a fraction, nested down as far as you like:

The list of integers [a_0; a_1, a_2, a_3, \dots] is the number. This unusual notation turns out to give the best rational approximations any number can have — better, in a precise sense, than the decimal system ever could.

How to build one

The algorithm is pure Euclidean algorithm in disguise. Take the whole-number part, subtract it off, flip the remainder, and repeat:

So \frac{45}{16} = [2; 1, 4, 3]. The integers 2, 1, 4, 3 are exactly the quotients Euclid's algorithm produces for \gcd(45, 16) — the continued fraction and the gcd are the same computation read two ways. For a rational number the list always terminates; for an irrational it runs forever.

Convergents: the best approximations

Truncating the list early gives a convergent — a rational that approximates x. The remarkable theorem is that each convergent is the best possible rational approximation for its size of denominator: no fraction with a smaller denominator gets closer.

For \pi, the convergents are 3,\ \frac{22}{7},\ \frac{333}{106},\ \frac{355}{113}, \dots The third, \frac{355}{113}, matches \pi to six decimal places using a three-digit denominator — an approximation so good it was known in 5th-century China.

The golden ratio: the worst-approximable number

The continued fraction also tells you which numbers are hardest to approximate by rationals. A large entry a_i means the previous convergent was already excellent (you barely needed the next term). So the number that is least approximable is the one with the smallest possible entries everywhere — all 1s:

This is the golden ratio. Its all-ones expansion makes it the most stubbornly irrational number there is — a fact that explains why sunflower seeds and pinecones space their spirals by the golden angle: it is the packing least prone to settling into a repeating, gappy rational pattern.

See also

• Greatest Common Divisor
• Diophantine Equation
• Number Theory