A continued fraction writes a number as a chain of integer parts and reciprocals. The convergents (partial evaluations) are the best rational approximations. Quadratic irrationals like sqrt(2) have periodic continued fractions, and this connects to Pell's equation.
Convergents as best approximations
sqrt(2) = [1; 2, 2, 2, ...]. The convergents 1/1, 3/2, 7/5, 17/12, 41/29, ... alternate above and below sqrt(2), getting closer each time. No fraction with a smaller denominator gets closer.
Scheme
; Continued fraction expansion of a rational number
(define (cf-rational p q)
(if (= q 0) (list)
(cons (quotient p q)
(cf-rational q (modulo p q)))))
(display "CF of 355/113 = ") (display (cf-rational 355113)) (newline)
; [3; 7, 16, 11] -- wait, this is actually [3; 7, 16]; 355/113 is the famous approximation to pi
(display "CF of 17/12 = ") (display (cf-rational 1712)) (newline)
; [1; 2, 2, 2] -- convergent of sqrt(2)
(display "CF of 41/29 = ") (display (cf-rational 4129)) (newline)
; [1; 2, 2, 2, 2] -- next convergent of sqrt(2); Evaluate a continued fraction [a0; a1, a2, ...]
(define (cf-eval coeffs)
(if (null? (cdr coeffs))
(list (car coeffs) 1) ; p/q as (p q)
(let* ((rest (cf-eval (cdr coeffs)))
(p (car rest))
(q (cadr rest)))
(list (+ (* (car coeffs) p) q) p))))
(let ((r (cf-eval (list 122222))))
(display "CF [1;2,2,2,2,2] = ")
(display (car r)) (display "/") (display (cadr r)))
Python
# Continued fractionsdef cf_rational(p, q):
"""Continued fraction expansion of p/q."""
coeffs = []
while q != 0:
coeffs.append(p // q)
p, q = q, p % q
return coeffs
def convergents(coeffs):
"""Compute convergents from CF coefficients."""
p_prev, p_curr = 0, 1
q_prev, q_curr = 1, 0
result = []
for a in coeffs:
p_prev, p_curr = p_curr, a * p_curr + p_prev
q_prev, q_curr = q_curr, a * q_curr + q_prev
result.append((p_curr, q_curr))
return result
print(f"CF of 355/113 = {cf_rational(355, 113)}")
# sqrt(2) = [1; 2, 2, 2, ...]
cf_sqrt2 = [1] + [2] * 10
convs = convergents(cf_sqrt2)
print("Convergents of sqrt(2):")
for p, q in convs[:6]:
print(f" {p}/{q} = {p/q:.10f}")
print(f" sqrt(2) = {2**0.5:.10f}")
Pell's equation
The equation x^2 - D y^2 = 1 (for non-square D) has infinitely many solutions. The fundamental solution comes from the convergents of the continued fraction of sqrt(D). For sqrt(2) = [1; 2, 2, ...], the convergent 3/2 gives 3^2 - 2(2^2) = 9 - 8 = 1.
Scheme
; Pell's equation: x^2 - D*y^2 = 1; Find solutions from convergents of sqrt(D); Convergents of [1; 2, 2, 2, ...] (sqrt(2))
(define (convergents-sqrt2 n)
(let loop ((k 0) (p-prev 0) (p-curr 1) (q-prev 1) (q-curr 0) (results (list)))
(if (>= k n)
(reverse results)
(let* ((a (if (= k 0) 12))
(p-next (+ (* a p-curr) p-prev))
(q-next (+ (* a q-curr) q-prev)))
(loop (+ k 1) p-curr p-next q-curr q-next
(cons (list p-next q-next) results))))))
(display "Convergents and Pell check (x^2 - 2y^2):") (newline)
(for-each
(lambda (pair)
(let ((x (car pair)) (y (cadr pair)))
(display " ") (display x) (display "/") (display y)
(display " -> ") (display x) (display "^2 - 2*")
(display y) (display "^2 = ")
(display (- (* x x) (* 2 y y))) (newline)))
(convergents-sqrt2 8))
; Solutions to Pell: where the value is 1 or -1