Euclid's algorithm on a 34 by 13 rectangle
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
Square-peeling on a 1 by φ rectangle
Euclid's game on 34 and 21
The whole game tree of Euclid's game from (7, 3)
Who wins Euclid's game, for every start up to 40
Consecutive Fibonacci numbers in Euclid's game
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
- 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
- consecutive Fibonacci positions alternate between win and loss ×1
- every interval the count isolates holds exactly one real root found separately ×1
- N is from 12 to 60 ×1
- N is read only by the gamegrid view ×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
- the count drops by exactly one across each real root ×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 polynomial is one of the named examples ×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 verdict follows the side of φ the ratio falls on ×1
- the view is one the family draws ×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
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.
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.
GeometryThe 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.
GeometryThe 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.
GeometryThe 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.
GeometryThe 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.
NumberThe 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.