A notebook that hides its setup

Continued fractions of the square root of 2 and of pi, with the setup code hidden and a long check's output hidden (Jupyter's own flags).

notebook · Python · intro · by Sagebrush · MIT license

number theory programming

Download (ZIP)Source on GitHub

Preview

A notebook that hides its setup

The first code cell holds the setup: the functions this notebook uses. Its code is hidden (Jupyter's source_hidden): you see a collapsed bar, and can open it to read or change it. It still runs, like any cell.

# Setup: continued fractions, exactly (integers and fractions only)
from fractions import Fraction
from math import isqrt


def cf_sqrt(n, terms=12):
    """The continued fraction of sqrt(n): a0; a1, a2, ... (periodic), by the classic integer recurrence."""
    a0 = isqrt(n)
    if a0 * a0 == n:
        return [a0]
    m, d, a, out = 0, 1, a0, [a0]
    while len(out) < terms:
        m = d * a - m
        d = (n - m * m) // d
        a = (a0 + m) // d
        out.append(a)
    return out


def cf_fraction(x, terms=8):
    """The continued fraction of a Fraction x (it ends: x is rational)."""
    out = []
    while len(out) < terms:
        a = x.numerator // x.denominator
        out.append(a)
        if x == a:
            break
        x = 1 / (x - a)
    return out


def convergents(cf):
    """p/q for each prefix of the continued fraction."""
    p0, q0, p1, q1 = 1, 0, cf[0], 1
    out = [Fraction(p1, q1)]
    for a in cf[1:]:
        p0, q0, p1, q1 = p1, q1, a * p1 + p0, a * q1 + q0
        out.append(Fraction(p1, q1))
    return out


def show(cf):
    print("[" + str(cf[0]) + "; " + ", ".join(map(str, cf[1:])) + "]")
    for c in convergents(cf):
        print(f"  {c.numerator}/{c.denominator}")

$2 = [1; 2, 2, 2, \dots]$ , and its convergents $p / q$ are the best rational approximations: each solves Pell's equation $p^{2} - 2 q^{2} = \pm 1$ .

show(cf_sqrt(2, 8))

[1; 2, 2, 2, 2, 2, 2, 2]

The convergents of $π$ include $22/7$ and $355/113$ (Zu Chongzhi's, good to six decimals). Here from a rational approximation of $π$ , exactly:

pi_ish = Fraction(314159265358979, 100000000000000)
show(cf_fraction(pi_ish, 5))

[3; 7, 15, 1, 292]
  3/1
  22/7
  333/106
  355/113
  103993/33102

The next cell checks Pell's equation for the first twenty convergents of $2$ . Its long output is hidden (Jupyter's outputs_hidden), since the last line says it all; open it to see every row.

for c in convergents(cf_sqrt(2, 20)):
    p, q = c.numerator, c.denominator
    print(p, q, p * p - 2 * q * q)
print("all +1 or -1:", all(abs(c.numerator**2 - 2 * c.denominator**2) == 1 for c in convergents(cf_sqrt(2, 20))))

1 1 -1
3 2 1
7 5 -1
17 12 1
41 29 -1
99 70 1
239 169 -1
577 408 1
1393 985 -1
3363 2378 1
8119 5741 -1
19601 13860 1
47321 33461 -1
114243 80782 1
275807 195025 -1
665857 470832 1
1607521 1136689 -1
3880899 2744210 1
9369319 6625109 -1
22619537 15994428 1
all +1 or -1: True

Files

main.ipynb (4251 bytes)

Open the ZIP's notebook in Sagebrush (File, Open) to run and change it.