Generator

Necklaces of 5 beads in 2 colours

A generator in the number library, called 34 times across 9 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.

necklace 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

Necklaces of 5 beads in 2 colours. Every string of beads, grouped by the rotations that carry one onto another.

A witness that 97 is prime: 5 has order 96

The largest order mod n, for n up to 200: only primes reach n − 1

A primality certificate for 1009: 8 nodes

The share of bases that witness a prime, for primes up to 2000

$The share of bases that witness a prime, for primes up to 2000. A scatter of φ(p − 1)/(p − 1) against p for the primes up to 2000, the fraction of bases that have the largest possible order.$

Every string of 5 beads in 2 colours

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.

Fermat's theorem holds at 3 ×549
the largest order mod 3 is λ(3) ×58
the primitive roots of 3 number φ(p − 1) ×29
the search and the rule agree at 2 ×29
1 to the power 4 is 1 modulo 15 ×28
1 to the power 13 − 1 is 1, which is Fermat's theorem ×12
the order of 1 divides 13 − 1 ×12
exactly φ(1) residues have order 1 ×8
the class of numbers sharing n/1 with n has φ(1) members ×6
the order of 2 divides λ(561) ×6
the order of 2 falls short of 561 − 1 ×6
the Wieferich primes to base 2 below 200000 ×6
the modulus is a whole number between 5 and 31 ×4
the powers of 2 run through every residue ×4
1009 has a primitive root ×3
11 to the 1008 is 1 mod 1009 ×3
Chernick's construction at k = 1 satisfies Korselt's divisibility ×2
no proper divisor of 4 works for every unit ×2
the base is a whole number between 2 and 12 ×2
the bound is a whole number between 12 and 42 ×2
the length is a whole number between 3 and 7 ×2
the number is a whole number between 6 and 24 ×2
the number of colours is a whole number between 2 and 4 ×2
a base passing every check exists exactly when the number is prime ×1
and exactly a of them are single ×1
and no smaller power along a prime is ×1
and reach each of them once ×1
and the largest order divides φ(n) ×1
and the number of non-constant classes is (a^p − a)/p ×1
at least one composite below 2000 survives every base ×1
at least one product was checked against every base rather than by the criterion alone ×1
at least one residue has order p − 1, which is what being cyclic means ×1
at least two composites below 2000 survive base 2 ×1
at least two values of k below 12 give three primes ×1
both verdicts occur inside the bound, so the table is deciding something ×1
every base coprime to 1729 returns 1 ×1
every class is a single string or a full ring of p ×1
every order divides the largest one ×1
every other class holds exactly p strings ×1
every string of the given length is drawn ×1
Mertens's estimate matches the exact sum of 1/p at a million ×1
more than one order occurs, so the picture is separating the residues ×1
not every residue is a generator, so the list is a selection ×1
only 1093 and 3511 keep their order ×1
p divides a^p − a, which is what the count just showed ×1
some of them are caught by another base, so the two columns differ ×1
the base is coprime to the modulus ×1
the classes account for every number from 1 to n ×1
the classes account for every string ×1
the classes of size one are exactly the constant strings ×1
the criterion and the exhaustive base test give the same verdict ×1
the drawn ring has as many beads as the base's order ×1
the figure draws every string, so there is a ceiling on how many ×1
the largest k searched is a whole number between 1 and 40 ×1
the length is prime ×1
the length is prime — the whole argument needs it to be ×1
the modulus is prime ×1
the modulus is prime, so every non-zero residue has an order ×1
the number has at least three divisors, so the identity is not trivial here ×1
the number is a prime below a million ×1
the number is a whole number below a million ×1
the number is composite — the criterion is about composites ×1
the only zeros are 1093 and 3511 ×1
the orbit closes ×1
the orders account for every residue ×1
the quotients are computed in exact whole numbers below 9,000 ×1
the units are counted, and there are φ(n) of them ×1
the view is one the family draws ×1
there are φ(13 − 1) generators ×1
there is more than one base to test ×1
λ(n) = n − 1 exactly when n is prime ×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

An order that proves a prime

Fermat's little theorem is a test that primes pass and composites mostly fail, and it can be fooled. Run backwards, it cannot. If some number a has order exactly n − 1 modulo n, then n is prime — because only a prime has n − 1 numbers to cycle through. Checking that takes the prime factors of n − 1, which need proofs of their own, and the proofs nest into a tree that anyone can check: Pratt's certificate, which shows every prime has a short proof of being one.

Algebra

Colourings nobody can tell apart

Sixteen ways to colour four corners in two colours, and only six of them are genuinely different. The count can be got by pooling the sixteen — or by never forming a single class and instead averaging how many colourings each motion leaves untouched.

Computation

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

Number

Necklaces that prove a theorem

Thread five beads in two colours, thirty-two ways. Two of them are all one colour; the other thirty fall into rings of five. That count, and nothing else, is Fermat's little theorem.

Number

One residue whose powers are all of them

Fermat's theorem says every order divides p − 1. It does not say that anything has order exactly p − 1, which is a separate and stronger claim — and what forces it is a count of how many numbers share each divisor with p − 1.

Algebra

The blocks a subgroup cuts out

Take any part of a group that is closed under composition, and it slices the whole group into blocks of its own size that do not overlap. Everything Lagrange's theorem says is arithmetic about that picture — and whether the blocks can be multiplied is a separate question with a surprising answer.

Number

The exponent that is smaller than Euler's

Euler's theorem raises every unit to the count of the units and gets one. The smallest exponent that works for all of them at once is often much smaller — and a composite is invisible to Fermat's test exactly when that smaller number divides n − 1.

Dynamics

The orbit written as a word

Cut the interval in two and record which half each step of an orbit lands in. The orbit becomes an infinite string of two letters, the map becomes the act of deleting the first letter, and questions about trajectories turn into questions about words.

Number

Two primes where Fermat holds twice

Fermat's theorem says p divides 2^(p−1) − 1. Usually p² does not. It does at 1093 and at 3511 and at no other prime anyone has found, in searches reaching past 10^19. The leftover, (2^(p−1) − 1)/p taken mod p, behaves like a random number, so a prime has about a one-in-p chance of the extra divisibility — and a random count with that chance grows so slowly that two by now is unremarkable, while nobody can prove there are any more, or that there are infinitely many primes where it fails.

The whole library · What the figures prove