Continued Fraction Expansion

A continued fraction represents a real number as a nested sequence of integer divisions:

x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}

written compactly as $x = [a_0; a_1, a_2, a_3, \ldots]$ , where $a_0 \in \mathbb{Z}$ and $a_1, a_2, \ldots$ are positive integers.

Computing the Expansion

The coefficients $a_i$ come from repeatedly peeling off the integer part and inverting the remaining fraction:

a_0 = \lfloor x \rfloor, \qquad x_1 = \frac{1}{x - a_0}, \qquad a_1 = \lfloor x_1 \rfloor, \qquad x_2 = \frac{1}{x_1 - a_1}, \ldots

If $x$ is rational, this process terminates after finitely many steps (it's exactly the Euclidean algorithm run on the numerator and denominator).
If $x$ is irrational, the expansion is infinite. If $x$ is additionally a quadratic irrational (root of a quadratic with integer coefficients), the expansion is eventually periodic.

from fractions import Fraction

def continued_fraction_rational(numerator, denominator):
    """Expand a rational number into its (finite) continued fraction coefficients."""
    coeffs = []
    a, b = numerator, denominator
    while b != 0:
        q = a // b             # integer part at this step
        coeffs.append(q)
        a, b = b, a - q * b    # same recurrence as the Euclidean algorithm
    return coeffs

print(continued_fraction_rational(415, 93))  # [4, 2, 6, 7]

def continued_fraction_real(x, n_terms=10, tol=1e-12):
    """Expand a real number into n_terms continued fraction coefficients."""
    coeffs = []
    for _ in range(n_terms):
        a = int(x // 1)        # floor, assuming x > 0
        coeffs.append(a)
        frac = x - a
        if abs(frac) < tol:    # x hit an exact integer; expansion terminates
            break
        x = 1 / frac           # invert the remainder for the next step
    return coeffs

print(continued_fraction_real(3.245, 6))  # [3, 4, 12, 3, 1, 1]

Convergents

Truncating the expansion at $a_k$ gives a rational approximation $p_k / q_k$ , called the $k$ -th convergent. These satisfy a simple linear recurrence:

p_{-1} = 1, \quad p_0 = a_0, \quad p_k = a_k p_{k-1} + p_{k-2}

q_{-1} = 0, \quad q_0 = 1, \quad q_k = a_k q_{k-1} + q_{k-2}

def convergents(coeffs):
    """Build all convergents p_k/q_k from a list of continued fraction coefficients."""
    p_prev2, p_prev1 = 1, coeffs[0]  # p_{-1}, p_0
    q_prev2, q_prev1 = 0, 1          # q_{-1}, q_0
    result = [(p_prev1, q_prev1)]
    for a in coeffs[1:]:
        p = a * p_prev1 + p_prev2    # linear recurrence for numerators
        q = a * q_prev1 + q_prev2    # linear recurrence for denominators
        result.append((p, q))
        p_prev2, p_prev1 = p_prev1, p
        q_prev2, q_prev1 = q_prev1, q
    return result

for p, q in convergents(continued_fraction_rational(415, 93)):
    print(f"{p}/{q} = {p/q:.6f}")
# 4/1 = 4.000000
# 9/2 = 4.500000
# 58/13 = 4.461538
# 415/93 = 4.462366

Each convergent $p_k/q_k$ is the best rational approximation to $x$ among all fractions with denominator $\le q_k$ — a fact that makes continued fractions the natural tool for rational approximation.

Periodic Expansions of Quadratic Irrationals

For $x = \sqrt{n}$ with $n$ a non-square positive integer, the expansion has the form

\sqrt{n} = [a_0; \overline{a_1, a_2, \ldots, a_k}]

where the bar denotes the repeating period. The coefficients can be generated without floating-point error using integer triples $(m_i, d_i, a_i)$ :

import math

def continued_fraction_sqrt(n):
    """Compute the periodic continued fraction coefficients of sqrt(n)."""
    a0 = int(math.isqrt(n))
    if a0 * a0 == n:
        raise ValueError("n must not be a perfect square")
    m, d, a = 0, 1, a0
    coeffs = [a0]
    while True:
        m = d * a - m          # next numerator term, kept as an exact integer
        d = (n - m * m) // d   # next denominator term, always divides evenly
        a = (a0 + m) // d      # next coefficient
        coeffs.append(a)
        if a == 2 * a0:        # the period always closes right before a == 2*a0
            break
    return coeffs

print(continued_fraction_sqrt(23))  # [4, 1, 3, 1, 8]  -> sqrt(23) = [4; 1,3,1,8]
print(continued_fraction_sqrt(2))   # [1, 2]           -> sqrt(2)  = [1; 2]

Worked Example

Expand $x = \frac{415}{93}$ .

Step	$a$	$b$	$q = \lfloor a/b \rfloor$	$r = a \bmod b$
1	415	93	4	43
2	93	43	2	7
3	43	7	6	1
4	7	1	7	0

So $\frac{415}{93} = [4; 2, 6, 7]$ , and the convergents $4,\ \frac{9}{2},\ \frac{58}{13},\ \frac{415}{93}$ approximate it with steadily increasing accuracy, the last one being exact.

Why It Matters

Rational approximation: convergents give the best possible rational approximations to irrational numbers for a given denominator size — the basis of calendar design, gear ratios, and musical tuning systems.
Pell's equation: the fundamental solution of $x^2 - ny^2 = 1$ comes directly from the convergents of the periodic continued fraction of $\sqrt{n}$ (see the related post on Pell's equation).
Euclidean algorithm: expanding a rational number is literally the Euclidean algorithm — the quotients at each division step are the continued fraction coefficients.
Number theory: continued fractions characterize quadratic irrationals (periodic) versus other irrationals, and underlie algorithms like Lagrange's for solving Pell-like equations.