Generator

The Stern–Brocot tree to depth 4

A generator in the number library, called 24 times across 6 essays. Below: what it draws at its defaults and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

mediant is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

The Stern–Brocot tree to depth 4. Every positive rational, each appearing exactly once, generated by taking mediants.

`show: "ford"`

Ford circles up to denominator 7. A circle of diameter one over q squared resting on each fraction p over q; neighbours touch.

`show: "farey"`

The Farey sequence of order 7. Every fraction in the unit interval with denominator at most n, marked on a line.

`show: "diatomic"`

Every positive rational, in one sequence. The first 32 terms of Stern's diatomic sequence as bars, with the ratios of consecutive terms beneath. Every ratio is in lowest terms, no two agree, and each term counts the hyperbinary representations of its index.

`show: "matrices"`

The tree as words in two matrices. 5 nodes of the Stern–Brocot tree, each as the word of turns reaching it, the matrix that word multiplies out to, its two columns as fractions, and the mediant of those columns.

`show: "approx"`

13 record approximations in 26 turns. The distance from π to each fraction the descent passes, against its denominator, on logarithmic axes. 13 of them beat every fraction with a smaller denominator.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

7/2 is in lowest terms ×108
the circles on 0/1 and 1/7 touch ×56
s(1) and s(2) are coprime ×48
the 1th ratio's numerator agrees with the Calkin–Wilf walk ×48
the ratio 1/1 appears once ×48
0/1 and 1/7 are Farey neighbours ×24
1/1 arrives already in lowest terms ×15
and its mediant 1/1 is already in lowest terms ×13
s(2) counts the hyperbinary representations of 1 ×12
the sequence has one entry per coprime pair up to 7 ×2
and at most its right bound ×1
and is closer to the target ×1
and its denominator does too ×1
and the path closes on the target ×1
circles that are not neighbours stay clear of each other ×1
each path is a word of at most eight L's and R's ×1
each record has a larger denominator than the last ×1
how many terms are drawn is a whole number between 8 and 64 ×1
how many turns are taken is a whole number between 6 and 34 ×1
no fraction is produced twice ×1
no two words produce the same matrix, so the tree never rejoins ×1
reading the drawing left to right reads the fractions in increasing order ×1
the depth is a whole number between 2 and 5 ×1
the descent passes at least three fractions within 1/q² of the target ×1
the descent produces several record approximations ×1
the drawing scale is a whole number between 200 and 400 ×1
the matrix for "L" has determinant ±1 ×1
the matrix for "LR" has determinant ±1 ×1
the matrix for "LRL" has determinant ±1 ×1
the matrix for "LRLR" has determinant ±1 ×1
the matrix for "LRLRL" has determinant ±1 ×1
the matrix for "R" has determinant ±1 ×1
the matrix for "RL" has determinant ±1 ×1
the matrix for "RLR" has determinant ±1 ×1
the matrix for "RLRR" has determinant ±1 ×1
the matrix for "RR" has determinant ±1 ×1
the matrix for "RRL" has determinant ±1 ×1
the matrix for "RRLR" has determinant ±1 ×1
the matrix for "the root" has determinant ±1 ×1
the mediant is at least its left bound ×1
the mode of the mediant family is one of tree, farey, ford, matrices, diatomic, approx ×1
the order is a whole number between 2 and 12 ×1
the target is one of phi, root2, pi, e ×1
the tree is full to its stated depth ×1
up to which index the hyperbinary count is checked is a whole number between 4 and 24 ×1

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Number

A tree that holds every triple

Three fixed matrices, applied to 3-4-5 over and over, produce every primitive Pythagorean triple there is — each of them once, none of them twice, and with no test for common factors anywhere in the procedure.

Number

Approached too fast to be algebraic

An algebraic number of degree d cannot be approached by fractions faster than the denominator's dth power. So a number that is approached faster than that is the root of no polynomial at all — and one can be built by choosing where its decimal digits go.

Number

Every fraction, exactly once

Take two fractions, add the tops and add the bottoms. That is not how fractions are added, it is not an average, and repeating it produces every positive rational exactly once, already in lowest terms.

Number

Every rational in one sequence

The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.

Number

The fractions that beat every smaller one

Walking down the tree towards a number produces a sequence of fractions closing in on it. Most of them are steps along the way; a few are the best approximations there are — closer than every fraction with a smaller denominator — and which few is decided by where the turns change direction.

Number

Two matrices that generate the tree

A node of the Stern–Brocot tree is not really a fraction — it is the pair of fractions it lies between. Written as the columns of a matrix, the two turns of the tree become two multiplications, and the determinant that kept everything in lowest terms becomes a property of a product.

The whole library · What the figures prove