Continued Fractions

Notation and the algorithm

A simple continued fraction of a real number x is an expression of the form

x = a₀ + ──────1──────
            a₁ + ────1────
                  a₂ + ──1──
                        a₃ + ⋯

compactly written x = [a₀; a₁, a₂, a₃, …]. The semicolon separates the integer part a₀ (which can be negative) from the partial quotients a₁, a₂, … which are positive integers. Every real number admits such an expansion, finite if and only if x is rational. The expansion is unique once we forbid trailing ones (e.g., [1; 2, 1] is rewritten [1; 3]).

The expansion is computed by repeated floor-and-reciprocate, the Euclidean algorithm in disguise:

x₀ = x
loop:
    aₙ = floor(xₙ)
    if xₙ is an integer: stop
    xₙ₊₁ = 1 / (xₙ − aₙ)

Each step extracts the integer part and inverts the remainder. For rational x = p/q, this terminates in O(log q) steps; the partial quotients are exactly the quotients in the Euclidean algorithm for gcd(p, q). For irrational x it runs forever, generating an infinite sequence.

Convergents and the recursion

The truncations p_n/q_n = [a₀; a₁, …, aₙ] are called convergents. They are computed by an elegant two-term recursion:

p₋₁ = 1, p₀ = a₀,    pₙ = aₙ · pₙ₋₁ + pₙ₋₂
q₋₁ = 0, q₀ = 1,     qₙ = aₙ · qₙ₋₁ + qₙ₋₂

From this recurrence, two crucial identities follow. First, gcd(pₙ, qₙ) = 1 — every convergent is in lowest terms. Second,

pₙ qₙ₋₁ − pₙ₋₁ qₙ = (−1)ⁿ⁺¹

which says consecutive convergents lie on opposite sides of x and are remarkably close together: |pₙ/qₙ − pₙ₋₁/qₙ₋₁| = 1/(qₙ qₙ₋₁). The signs alternate, so the convergents pinch x from both sides.

Best rational approximation

The defining property of convergents — and the reason they show up everywhere in number theory — is the following:

If pₙ/qₙ is a convergent of x, then for every rational p/q ≠ pₙ/qₙ
with q ≤ qₙ, we have |x − p/q| > |x − pₙ/qₙ|.

In words: no rational with denominator at most qₙ is closer to x than the nth convergent. Convergents are best-possible approximations among rationals up to a given denominator, with a known error bound:

|x − pₙ/qₙ| < 1/(qₙ · qₙ₊₁) < 1/(aₙ₊₁ qₙ²)

Big partial quotients aₙ₊₁ make the previous convergent unusually good. This is exactly what happens with π.

Worked example: continued fraction of √2

Let us run the algorithm on √2 ≈ 1.41421356237.

n=0:  x₀ = √2 = 1.41421...
      a₀ = 1
      x₁ = 1/(√2 − 1)
         = (√2 + 1) / ((√2 − 1)(√2 + 1))     [rationalise]
         = (√2 + 1) / (2 − 1)
         = √2 + 1 = 2.41421...

n=1:  a₁ = 2
      x₂ = 1/(√2 + 1 − 2) = 1/(√2 − 1) = √2 + 1   [same as x₁!]

n=2:  a₂ = 2, x₃ = √2 + 1
n=3:  a₃ = 2, x₄ = √2 + 1
   ⋮  the loop has closed.

So  √2 = [1; 2, 2, 2, 2, …] = [1; 2̄].

Now compute the convergents:

n   aₙ   pₙ                       qₙ                       pₙ/qₙ              |√2 − pₙ/qₙ|
─   ──   ─────────────────        ─────────────────         ─────────          ─────────────
0   1    p₀ = 1                   q₀ = 1                    1/1 = 1.0000000   4.14 × 10⁻¹
1   2    p₁ = 2·1 + 1 = 3         q₁ = 2·1 + 0 = 2          3/2 = 1.5000000   8.58 × 10⁻²
2   2    p₂ = 2·3 + 1 = 7         q₂ = 2·2 + 1 = 5          7/5 = 1.4000000   1.42 × 10⁻²
3   2    p₃ = 2·7 + 3 = 17        q₃ = 2·5 + 2 = 12         17/12 = 1.4166667 2.45 × 10⁻³
4   2    p₄ = 2·17 + 7 = 41       q₄ = 2·12 + 5 = 29        41/29 = 1.4137931 4.20 × 10⁻⁴
5   2    p₅ = 2·41 + 17 = 99      q₅ = 2·29 + 12 = 70       99/70 = 1.4142857 7.20 × 10⁻⁵
6   2    p₆ = 2·99 + 41 = 239     q₆ = 2·70 + 29 = 169      239/169 = 1.41420 2.07 × 10⁻⁵

The error decreases by a factor of about 5.83 = 1 + 2√2 each step — exactly what the recurrence predicts for the periodic [1; 2̄] expansion. Each convergent is the best rational approximation of √2 with denominator at most qₙ. There is no fraction with denominator ≤ 169 closer to √2 than 239/169.

The pairs (qₙ, pₙ) = (1, 1), (2, 3), (5, 7), (12, 17), (29, 41), (70, 99), … are the side-and-diagonal numbers from Euclid's Elements: solutions to p² − 2q² = ±1, the Pell equation for D = 2. Squaring (3, 2) ↔ (3 + 2√2)² = 17 + 12√2 gives the next solution (17, 12), and so on. The continued fraction generates them automatically.

Famous continued fractions

Number	Continued fraction	Notable convergents	Comment
√2	[1; 2, 2, 2, …]	1, 3/2, 7/5, 17/12, 41/29	Period 1; gives Pell solutions
√3	[1; 1, 2, 1, 2, 1, 2, …]	1, 2/1, 5/3, 7/4, 19/11, 26/15	Period 2
φ (golden ratio)	[1; 1, 1, 1, 1, …]	1, 2/1, 3/2, 5/3, 8/5 (Fibonacci ratios)	Slowest-converging CF — "most irrational"
e	[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …]	2, 3, 8/3, 11/4, 19/7, 87/32, 106/39	Pattern aₙ = 2k for n = 3k+1, else 1
π	[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, …]	3, 22/7, 333/106, 355/113, 103993/33102	No known pattern; the 292 makes 355/113 outstanding
ln 2	[0; 1, 2, 3, 1, 6, 3, 1, 1, 2, 1, …]	0, 1, 2/3, 7/10, 9/13, 61/88	No closed-form pattern
(1+√5)/2 (φ again)	[1; 1, 1, 1, …]	F_{n+1}/F_n	Convergents are Fibonacci ratios

Why is 355/113 spectacular? Because the next partial quotient after [3; 7, 15, 1] is 292 — large. The error bound becomes |π − 355/113| < 1/(292 · 113²) = 1/3,728,468 ≈ 2.7 × 10⁻⁷, which gives π correct to seven significant figures from a fraction with three-digit denominator. The Chinese astronomer Zu Chongzhi found 355/113 in the 5th century by trial; the continued fraction explains why it works so well.

Lagrange's periodicity theorem

One of the most beautiful results in elementary number theory:

The continued fraction of x is eventually periodic
⟺ x is a quadratic irrational (root of irreducible ax² + bx + c with a, b, c ∈ Z).

Proved by Lagrange in 1770. The forward direction is easy: a periodic CF gives a fixed-point equation x = (px + r)/(sx + t) for integer p, r, s, t, which rearranges to a quadratic. The reverse — that every quadratic irrational has a periodic CF — is harder; it uses the boundedness of conjugate quadratic surds under the CF iteration.

So square roots of non-square integers all have periodic continued fractions: √7 = [2; 1, 1, 1, 4̄], √13 = [3; 1, 1, 1, 1, 6̄], √19 = [4; 2, 1, 3, 1, 2, 8̄]. The period length grows somewhat erratically: √61 has period 11, √109 has period 15. The algorithm to compute the period is direct integer arithmetic and runs in O(√D log D) time.

Pell's equation

Pell's equation x² − D y² = 1 (D > 0, not a perfect square) has positive integer solutions, infinitely many, all generated from a fundamental solution. Continued fractions deliver the fundamental solution directly. If √D = [a₀; a₁, …, aₚ] has period p, then:

• If p is even, (x, y) = (pₚ₋₁, qₚ₋₁) — the convergent immediately before the period repeats — solves x² − Dy² = 1.
• If p is odd, the same convergent solves x² − Dy² = −1; its square (xₚ₋₁ + qₚ₋₁ √D)² gives the fundamental solution to x² − Dy² = 1.

For D = 13: √13 = [3; 1, 1, 1, 1, 6̄], period 5 (odd). Convergents: 3, 4, 7/2, 11/3, 18/5. The "before-period" convergent is 18/5, with 18² − 13·5² = 324 − 325 = −1. Squaring (18 + 5√13) gives (18 + 5√13)² = 649 + 180√13, so the fundamental solution to x² − 13y² = 1 is (649, 180): 649² − 13 · 180² = 421201 − 421200 = 1.

This algorithm is dramatically faster than brute search. For D = 61, the fundamental solution is (1766319049, 226153980), beyond reach of trial division but trivial via continued fractions.

Variants and extensions

• Generalised continued fractions. Allow numerators other than 1: x = b₀ + a₁/(b₁ + a₂/(b₂ + …)). Many classical analytic identities take this form. Example: π/4 = 1/(1 + 1²/(2 + 3²/(2 + 5²/(2 + …)))) (Brouncker, 1655). Convergence is no longer guaranteed; you need monotonicity or Pringsheim-type conditions.
• Continued fractions for functions. Approximate analytic functions by f(x) = b₀(x) + a₁(x)/(b₁(x) + a₂(x)/(b₂(x) + …)). Padé approximants can be encoded as CFs; CF expansions for tan(x), erf(x), and elliptic integrals converge faster than Taylor series in many regions.
• Negative continued fractions. [a₀; b₁, b₂, …] with subtraction: a₀ − 1/(b₁ − 1/(b₂ − …)). Used in Hirzebruch-Jung resolution of singularities, where they give a unique normal form for cyclic quotient surface singularities.
• Stern-Brocot tree and Farey sequences. Binary tree of all positive rationals, related to convergents: the path from root to p/q encodes the continued fraction. Farey sequences (rationals in [0,1] up to denominator n, in order) are the "frontier" of best rational approximations, also captured by continued fractions.
• Multidimensional continued fractions. Jacobi-Perron, Brun, and Selmer algorithms extend to simultaneous Diophantine approximation of (x₁, …, xₙ). They generate convergents that approximate all coordinates simultaneously, but lack the optimality of the 1D case.

Where continued fractions show up

• Calendar design. The tropical year is 365.2421875 days. Continued fraction: [365; 4, 7, 1, 3, 24, …]. Convergents give 365 days (the wrong year), 1461/4 (Julian: leap year every 4 years), 10592/29 (1 leap day every 29 of 4-leap-year cycles → close to Gregorian), 47651/130 (more accurate still). The Gregorian rule (skip leap year on centuries not divisible by 400) is a continued-fraction approximation to the tropical year.
• Audio and gear ratios. Designing a planetary gear with reduction ratio close to a target r requires picking integer tooth counts (a, b) with a/b ≈ r. Continued fractions give the smallest gears achieving any given accuracy. Mechanical clocks and orrery designers used this for centuries; modern robotics still uses it for cycloidal drives.
• Cryptanalysis: Wiener's attack on RSA. If the RSA private exponent d is small (less than N^{0.25}/3), Wiener (1990) showed d is one of the convergents of e/N, and so can be recovered from the public key in polynomial time via the continued fraction algorithm. This forces RSA implementations to use sufficiently large d.
• Number-theoretic algorithms. The Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm — central to integer factorisation, polynomial factorisation, and post-quantum cryptography — generalises the continued-fraction algorithm to higher dimensions. CFRAC, the original sub-exponential factorisation algorithm of Morrison and Brillhart (1975), used continued fractions of √N to find smooth factor relations.
• Music theory and tuning systems. Equal temperament approximates 7 octaves with 12 perfect fifths; the equation 12 · log₂(3/2) ≈ 7 has continued fraction analysis. The 53-tone temperament (53 fifths ≈ 31 octaves) is the next convergent and gives nearly exact fifths and major thirds; it has been advocated by some microtonal composers.

Common pitfalls

• Confusing the recursion indices. The convergent recurrence pₙ = aₙ pₙ₋₁ + pₙ₋₂ uses the new aₙ multiplied by the previous numerator. Off-by-one indexing is the most common error in implementations. Double-check against known cases — the first three convergents of √2 must be 1, 3/2, 7/5.
• Forgetting the rational case ambiguity. Every rational has two continued fraction expansions: [a₀; a₁, …, aₙ] and [a₀; a₁, …, aₙ − 1, 1]. Standard convention forbids trailing 1, making expansion unique. Software libraries differ on which they output.
• Floating-point drift in long expansions. Computing the CF of an irrational from a double-precision approximation gives only the first 15–16 partial quotients reliably. After that the truncation error in the input dominates and you produce noise. For long expansions, use exact arithmetic (continued fractions of quadratic surds via integer arithmetic; CFs of π via series-based algorithms with provable error bounds).
• Reading "best approximation" too narrowly. Convergents are best in the sense |x − p/q| < |x − p′/q′| for q′ ≤ qₙ. There are intermediate fractions ("semi-convergents") that may be better in absolute error per unit denominator. The Stern-Brocot mediant interpolates between consecutive convergents.
• Assuming famous numbers have nice CF patterns. e has a beautiful pattern; π does not. The continued fraction of π has been computed to billions of partial quotients with no recognisable structure. Khinchin's theorem suggests the geometric mean of the partial quotients of a "random" real is K ≈ 2.685; π's empirical mean matches K, suggesting it is statistically generic.