Continued Fractions

A continued fraction represents a real number as a convergent sequence of rationals. In contests they show up for best rational approximations, Euclidean-algorithm tricks, Stern–Brocot / Calkin–Wilf trees, and floor-sum formulas.

This lesson follows CP-Algorithms — Continued Fractions.

Prerequisites: GCD / Euclidean algorithm, basic number theory.

Representation

For integers a₀, a₁, …, aₖ with a₁, …, aₖ ≥ 1,

r = a₀ + 1/(a₁ + 1/(… + 1/aₖ))  =  [a₀; a₁, …, aₖ]

Every rational has exactly two expansions (replace trailing aₖ by aₖ−1, 1):

r = [a₀; …, aₖ, 1] = [a₀; …, aₖ + 1]

For irrationals, the infinite expansion is unique.

Complete quotients: sₖ = [aₖ; aₖ₊₁, …]. Then r = [a₀; …, aₖ₋₁, sₖ] and

aₖ = ⌊sₖ⌋ ,   sₖ₊₁ = (sₖ − aₖ)⁻¹

For sₖ = p/q, this is exactly Euclidean division: sₖ₊₁ = q / (p mod q).

Implementation = Euclidean algorithm

vector<int> fraction(int p, int q) {
    vector<int> a;
    while (q) {
        a.push_back(p / q);
        tie(p, q) = make_pair(q, p % q);
    }
    return a;
}

def fraction(p, q):
    a = []
    while q:
        a.append(p // q)
        p, q = q, p % q
    return a

Length is O(log min(p, q)). Convergents pₖ/qₖ are always coprime.

🧪 Euclidean CF for 43/19

Check: representation

Quiz

Continued fraction basics

1 / 4

Computing [a₀; a₁; …] for p/q uses the same steps as…

Pick an answer to see if you are right.

Convergents

Partial fractions rₖ = [a₀; …, aₖ] = pₖ/qₖ satisfy the recurrence (with p₋₂=0, p₋₁=1, q₋₂=1, q₋₁=0):

pₖ = aₖ pₖ₋₁ + pₖ₋₂
qₖ = aₖ qₖ₋₁ + qₖ₋₂

pair<vector<int>, vector<int>> convergents(vector<int> a) {
    vector<int> p = {0, 1}, q = {1, 0};
    for (int it : a) {
        p.push_back(p.back() * it + p[p.size() - 2]);
        q.push_back(q.back() * it + q[q.size() - 2]);
    }
    return {p, q};
}

Semiconvergents interpolate between consecutive convergents; best approximations with bounded denominator come from convergents and semiconvergents.

🧪 Build convergents for [2;3,1,4]

Key convergence facts

|r − pₖ/qₖ| ≤ 1/(qₖ qₖ₊₁) ≤ 1/qₖ²
pₖ qₖ₋₁ − pₖ₋₁ qₖ = (−1)^(k−1)

Convergents alternate above/below r. That is why continued fractions give sharp rational approximations.

Stern–Brocot and Calkin–Wilf trees

Stern–Brocot: binary search tree of positive rationals. Mediant (a+c)/(b+d) from parents a/b and c/d. The path [a₀; a₁, …, aₖ, 1] encodes left/right moves — continued fraction digits are run-lengths of the index bits.

Calkin–Wilf: root 1/1; children of p/q are p/(p+q) and (p+q)/q. Same rationals as Stern–Brocot in BFS order, but not sorted — BFS index differs by bit reversal.

Both connect to mediants and the convergent recurrence.

Why contests care

Pattern	Continued-fraction tool
Compare / match a rational to [aᵢ]	Euclidean expansion
Best p/q with q ≤ Q	Convergents & semiconvergents
Lexicographically smallest (x,y) in an open interval of slopes	Stern–Brocot / middle between bounds
⌊Ai + B⌋ sums, modular progressions	Complete quotients, LFTs
Quadratic irrationals	Eventually periodic expansion

Interactive: build [a₀; a₁; …]

Step through (p, q) → (q, p mod q) and watch convergents update.

Check: convergents & trees

Quiz

Convergents and trees

1 / 4

The error bound |r − pₖ/qₖ| is at most…

Pick an answer to see if you are right.

Practice drills

Activity: Build expansion

Given p q, print the Euclidean quotients a₀ a₁ … (space-separated).

Contest problems

UVa 834 — Continued Fractions

Judge: UVa 834

Classic conversion between a decimal / rational and its continued fraction form.

Why this lesson?

Direct application of the Euclidean expansion and convergent evaluation.

Cheat sheet

Task	Approach
Expand p/q	Euclid → quotients
Evaluate [a₀;…;aₖ]	Bottom-up or convergent recurrence
k-th convergent	pₖ = aₖ pₖ₋₁ + pₖ₋₂
Best approx with q ≤ Q	Scan convergents + semiconvergents
Fraction between two bounds	Stern–Brocot walk / middle
Sum of floors	Complete quotients + LFT (see full CP-Algorithms article)

Previous: Centroid Decomposition · Bit Manipulation

Source: CP-Algorithms — Continued Fractions