Generator

The Stern–Brocot tree to depth 4

A generator in the number library, called 52 times across 11 essays. Below: what it draws with nothing chosen 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.

With nothing chosen

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

Every denominator has a fraction with small quotients

The denominators each bound misses

The surplus of fractions over denominators

Thousands of good fractions for a typical denominator

Rarer at every size, and never absent

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.

?(1/11) is the binary fraction in the same position ×1023
0/1 and 1/13 have determinant one and nothing simpler between them ×359
3/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 1th arc crossed is the descent's 1th interval ×10
run 1 of the turns is the continued fraction's quotient ×5
the identity for n ≡ 3 (mod 4) gives 4/n ×3
the sequence has one entry per coprime pair up to 7 ×2
? of the expansion of all ones is 2/3 ×1
? of the expansion of all twos is 2/5 ×1
?(1 − x) = 1 − ?(x) ×1
?(x/(1 + x)) = ?(x)/2 ×1
|M(x)| stays below √x throughout the range drawn ×1
√2 − 1 has every quotient two ×1
4/n is a sum of three unit fractions for every n drawn ×1
above 100, the fewest ways belong to a prime that leaves 1 on division by 24 ×1
and at most its right bound ×1
and is closer to the target ×1
and it is within a per cent of 3n²/π² by the end ×1
and its denominator does too ×1
and so do the three fractions found by search ×1
and the path closes on the target ×1
and their lengths add to one ×1
circles that are not neighbours stay clear of each other ×1
depth d cuts the interval into 2^d pieces ×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
every denominator up to 3,000 has a fraction with quotients at most 5 ×1
every prime ≡ 1 (mod 24) up to the limit has a three-term decomposition ×1
every prime has at least one good fraction and the share is a share ×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
M(10) = 1 − 1 − 1 + 0 − 1 + 1 − 1 + 0 + 0 + 1 = −1 ×1
n leaves remainder 1 on division by 4 and is small enough to draw ×1
n times the sum of squared misfits stays below one across the orders drawn ×1
neighbouring Farey fractions have cross-difference one ×1
neighbouring Farey fractions have determinant one ×1
neighbouring nodes have determinant one ×1
no denominator up to 100,000 lacks a fraction with quotients at most 5 ×1
no fraction is produced twice ×1
no two words produce the same matrix, so the tree never rejoins ×1
only the class of 1 mod 24 escapes the three identities ×1
reading the drawing left to right reads the fractions in increasing order ×1
the chain from 4/n with n ≡ 1 (mod 4) has four steps ×1
the count is the length of the generated sequence ×1
the counting exponent approaches twice the dimension ×1
the denominator has a fraction with quotients at most 5 ×1
the denominator is a whole number from 11 to 100,000 ×1
the depth is a whole number between 2 and 5 ×1
the depth of the tree checked is a whole number between 3 and 14 ×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 endpoint each crossed arc keeps spells the descent's word ×1
the Farey fractions, placed on the circle and added, give the Mertens function ×1
the Farey order is between 3 and 6 ×1
the four gaps add up to 4/n ×1
the function never decreases ×1
the largest denominator drawn is a whole number between 5 and 30 ×1
the length carrying half the rise falls with depth ×1
the line crosses exactly as many arcs as the descent has intervals ×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, tessellation, questionmark, singular, fareydisc, franel, landau, mertens, expsum, fareycount, estree, esneighbours, eschains, escount, esclasses, eshard ×1
the number is one of phi, root2, pi, e ×1
the order is a whole number between 2 and 12 ×1
the path fits the drawing ×1
the search's largest fraction is the tree's first gap ×1
the target is one of phi, root2, pi, e ×1
the total misfit grows like the square root of the order ×1
the tree has 2^D − 1 nodes to depth D ×1
the tree is full to its stated depth ×1
the tree takes two steps when n ≡ 3 (mod 4) and four when n ≡ 1 ×1
the typical count grows like q to the power 2δ − 1 ×1
the window is a sub-interval of the unit interval ×1
three unit fractions suffice for every n drawn ×1
two to six increasing depths, up to 18 ×1
up to which index the hyperbinary count is checked is a whole number between 4 and 24 ×1
with nothing left over in the other direction ×1
with quotients at most 4 only 6, 54 and 150 fail up to 100,000 ×1
φ − 1 has every quotient one ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Number

A small quotient for every denominator

Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.

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

How evenly the fractions spread

List every fraction between nought and one with denominator at most n, in order. They spread across the interval almost evenly, and how fast the unevenness shrinks as n grows is — exactly, provably — the Riemann hypothesis. The link runs through a second fact: set the fractions round a circle and add them as arrows, and what is left is a whole number.

Number

The arcs a line crosses on its way to a number

Draw a semicircle over every pair of neighbouring fractions and the half-plane above the number line is cut into curved triangles that never overlap. A straight line dropped towards any number crosses those arcs one after another, and the arcs it crosses, and the side it leaves each triangle by, are exactly the steps of the Stern–Brocot descent towards that number.

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

The function that sends fractions to binary

The Stern–Brocot tree and the tree of binary fractions have exactly the same shape, so there is a function that sends each fraction to the binary fraction in the same position. It is continuous and increasing, it turns every quadratic irrational into an ordinary fraction, and it does all of its rising on a set of numbers so thin that at almost every point its slope is nought.

Number

Three unit fractions for every four over n

Two neighbouring fractions in the tree always differ by a unit fraction, so stepping down the tree writes any fraction as a sum of them — four over n in at most four steps. Erdős and Straus asked in 1948 whether three always suffice. Three identities settle every n except those leaving remainder 1 on division by 24, a search settles every one anyone has tried, and nobody has a proof.

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