Generator

Euclid's algorithm on a 34 by 13 rectangle

A generator in the geometry library, called 35 times across 8 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.

euclid 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

Euclid's algorithm on a 34 by 13 rectangle. The rectangle is tiled by peeling off the largest square that fits, again and again, until nothing is left.

Square-peeling on a 1 by φ rectangle

Two curves with five crossings: x⁶ + (44/31)y³ − y and its mirror

The second equation read along the first curve

Where in Haas's family the five solutions occur

The number of positive solutions at degree 6, as c changes

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.

the smallest square has side gcd(34, 13) ×4
the squares tile the 34 by 13 rectangle ×4
a ≥ b ≥ 1 are whole numbers, a at most 90 ×1
a ≥ b ≥ 1, a at most 12 ×1
a and b are read by the tiling and the two game views ×1
a count ×1
a quartic with signs ++−++ ×1
and with the rule that the first run longer than one decides ×1
at is a short list of whole points ×1
at is read only by the sturmtable view ×1
coeffs is read only by the descchain, descproof views ×1
consecutive Fibonacci positions alternate between win and loss ×1
coords is plain or corner ×1
coords is read only by the fewcurves view ×1
d is a whole number from 3 to 60 ×1
d is read only by the fewcount view ×1
deg is read only by the descgap view ×1
each solution satisfies both equations ×1
every degree in the list has a band of five ×1
every interval the count isolates holds exactly one real root found separately ×1
every polynomial found obeys the rule ×1
five sign changes along the curve ×1
for this polynomial the bound is attained ×1
Haas's c = 1.1 lies in the band at d = 54 ×1
N is from 12 to 60 ×1
N is read only by the gamegrid view ×1
never more than five, as Li, Rojas and Wang proved ×1
no polynomial has more positive roots than sign changes ×1
p(−x) is never above p(x) for positive x ×1
poly is read only by the sturm, sturmtable, isolate views ×1
range is an interval [lo, hi] ×1
range is read only by the sturm view ×1
Rolle: one more root at most than the next member ×1
system is read only by the fewcurves, fewtrace views ×1
the count drops by exactly one across each real root ×1
the count reaches five ×1
the drawn verdict is the searched one ×1
the drop from −∞ to +∞ is the number of distinct real roots ×1
the halving isolates every real root ×1
the leftover strip is still there after every pass ×1
the only pairs never found are the two Grabiner proved impossible ×1
the polynomial is one of the named examples ×1
the positive roots found on the graph are the ones Sturm's chain counts ×1
the rule's excess is never negative and always even ×1
the search agrees with the golden-ratio rule ×1
the squares peeled at each pass are the continued fraction of the ratio ×1
the system has five positive solutions ×1
the system is one of the two named ×1
the two general bounds for n = 2, k = 3 ×1
the verdict follows the side of φ the ratio falls on ×1
the view is one the family draws ×1
trials is read only by the descgap view ×1
two positive roots force two negative ones ×1
upTo is from 5 to 11 ×1
upTo is read only by the gamefib view ×1
V(lo) − V(hi) equals the number of distinct real roots found separately ×1
whole coefficients, highest first, leading positive and constant non-zero ×1
with every root real the rule is exact ×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 fraction that never closes

Euclid's algorithm throws away everything except the number of squares it peeled at each step. Those counts are a second name for the number it started from — one that terminates exactly when the ratio is a ratio.

Geometry

The oldest algorithm, drawn as a tiling

Euclid's method for finding a greatest common divisor is usually presented as a loop. It is also a way of tiling a rectangle with squares, and the tiling explains why it works.

Geometry

Five where four were promised

In one unknown, a polynomial with three terms has at most two positive roots, whatever its degree. The natural guess for two equations in two unknowns, each with three terms, was two times two: four. It is wrong. Bertrand Haas found two such equations in 2002 whose curves cross five times in the positive quadrant, all five crowded within a tenth of one corner, and five turned out to be the most there can ever be.

Geometry

The player who meets the first long run

Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.

Geometry

The rectangle that eats itself

Cut a square off a golden rectangle and what is left is a golden rectangle. That single property is the whole of the golden ratio, and it explains both what the number really does and most of what is wrongly claimed for it.

Geometry

The remainders that count the roots

Run Euclid's algorithm on a polynomial and its derivative, flipping the sign of each remainder, and write down the signs of the whole chain at any point. The number of sign changes drops by exactly one each time the point passes a real root — so the roots in any interval can be counted, exactly, without finding a single one.

Number

The square that cannot shrink

The usual proof that the square root of two is irrational is about even and odd numbers. There is a proof about squares instead, in which a supposed solution is folded into a smaller one — and the folding is a drawing.

Geometry

What the signs allow

Descartes' rule reads the signs of a polynomial's coefficients and bounds its positive roots by how often they change — a bound set by the number of terms, not the degree, and proved by nothing more than Rolle's theorem. Each count the rule allows can be had. But not every pair of counts, positive and negative, that the rule allows together can be had together: the first combination that never occurs is at degree four, and the list of impossible ones is still being worked out.

The whole library · What the figures prove