Generator

The sieve of Eratosthenes below 100

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

sieve 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 sieve of Eratosthenes below 100. A grid of the whole numbers with the composites struck out by the prime that removes them.

`show: "bertrand"`

Between every number and its double. The interval from n to twice n, drawn for n up to 26, with the primes inside each marked. Every interval contains at least one.

`show: "pnt"`

`show: "gaps"`

The gaps between primes below 300. One bar per consecutive pair of primes, its height the distance between them.

`show: "counts"`

π(x) below 3000. A staircase counting the primes, with x over the natural logarithm of x beside it.

`show: "product"`

The sieve as a product, and the sum over the primes. The whole numbers up to 60, with those built only from 2, 3, 5 marked — the numbers the product of three geometric series multiplies out to. Beside them, the sum of the reciprocals of the primes, which grows without bound.

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 class 0 shares a factor with 4, so it can hold at most the factor itself ×20
211 leaves remainder 1 on division by 2 ×10
the limit is a whole number between 10 and 400 ×5
2 classes share no factor with 4 ×4
the staircase ends at π(3000) ×4
every listed prime is already in the class 3 mod 4 ×2
so some prime factor of it is 3 mod 4 — the classes multiply, and a product of ones is one ×2
the class 3 leads at almost every bound ×2
the modulus is a whole number between 3 and 14 ×2
the number built is 3 mod 4 ×2
a Mersenne prime has a prime exponent ×1
a square left unstruck holds a prime, and a struck one does not ×1
an even truncation is an upper bound ×1
and 168 below a thousand ×1
and an odd one a lower bound ×1
and every combination of exponents appears once ×1
and it tracks the logarithm of a logarithm to within a twelfth throughout ×1
and modulo three it never falls behind over this range ×1
and over the last decade of the range the diverging sum gains more than twice as much ×1
and some of the lower bounds are negative, which is no bound at all ×1
and the first bound at which it does not is 26,861 ×1
and the number of them in the interval is never far below n / ln n ×1
and the one prime it holds divides the modulus ×1
and the ratio to x / ln x comes down as x grows ×1
and the twin pairs track theirs ×1
and there are almost none of them in this range ×1
and they hold them in near-equal numbers, which is more than Dirichlet's theorem claims ×1
between two and five odd primes are listed ×1
both classes hold primes below the bound ×1
each is near the share an even split would give ×1
every class coprime to the modulus holds primes ×1
every interval from n to 2n holds a prime ×1
every prime below the bound lands in exactly one class ×1
every prime factor of one more than a square of an even number is 1 mod 4 ×1
every prime factor of the constructed number is outside the list ×1
multiplying the factors out gives exactly the sum over the numbers they build ×1
no listed prime divides it ×1
one gap between each consecutive pair ×1
the bound the postulate is checked to is a whole number between 100 and 50000 ×1
the column count is a whole number between 4 and 25 ×1
the construction is the one that subtracts or the one that squares ×1
the count runs above x / ln x over this range ×1
the factorisation multiplies back to the number built ×1
the factors are between 2 and 4 primes ×1
the full inclusion-exclusion agrees with the count made by sifting ×1
the gaps add up to the distance from 2 to the last prime ×1
the grid of whole numbers drawn is a whole number between 24 and 144 ×1
the largest bound counted is a whole number between 5000 and 200000 ×1
the largest number sieved is a whole number between 100000 and 2000000 ×1
the largest prime sifted by is a whole number between 11 and 43 ×1
the list is between two and six primes ×1
the logarithmic integral runs above the count at every checkpoint drawn ×1
the marked checkpoints are whole numbers inside the range ×1
the number built stays inside exact arithmetic ×1
the number of intervals drawn is a whole number between 6 and 40 ×1
the numbers marked are exactly those the product builds ×1
the partial sums swing far past the answer before settling ×1
the pass number is between 0 and 8 ×1
the power each factor is truncated at is a whole number between 2 and 5 ×1
the primes 1 mod 4 are about half of all of them ×1
the primes one more than a square track the conjectured count ×1
the race is drawn modulo three or four ×1
the range sifted is a whole number between 10000 and 1000000 ×1
the range the sum over primes is drawn to is a whole number between 1000 and 1000000 ×1
the sieve found every prime below the bound ×1
the squares left standing below 100 are the primes ×1
the sum of the reciprocals of the primes keeps growing ×1
the sum over all primes has passed 2.8 and is still climbing ×1
the view is one the family draws ×1
there are 25 primes below 100 ×1
while the ratio to the logarithmic integral is nearer one by more than a factor of four ×1
while the sum over the twins is still under 1.8 ×1
π(x) stays above x / ln x throughout this range ×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

Always one before the double

A density says what happens on average and permits long empty stretches. This says something a density cannot — that the stretch from any number to twice it contains a prime, at every scale, without exception.

Number

Counting what has no formula

There is no expression that gives the nth prime, and yet the number of primes below a bound is predictable to within a fraction of a per cent — by a function that is not a formula for the primes but an integral of the wrong-looking quantity.

Number

The primes are what is left over

Eratosthenes' sieve does not find the primes. It removes everything else, one prime at a time, and whatever survives is prime by default — which is a strange way to reach the most studied objects in arithmetic.

Number

Every class, and in equal shares

Euclid's argument aimed at a residue class reaches some classes and stalls at others. The theorem covering all of them is Dirichlet's, its proof abandons arithmetic entirely for analysis, and what it proves is stronger than infinitude — the classes are equal, though not at any point anybody has counted.

Number

Infinitely many of one kind

Euclid's argument produces a prime nobody had listed, and says nothing about what it looks like. Ask for infinitely many primes ending in 3, or leaving a remainder of 1 on division by 4, and the same construction has to be aimed — and for most targets nobody knows how to aim it.

Number

There is no last prime

Euclid's argument is often described as producing a new prime from any finite list. It does not, and the number it builds is frequently composite — which makes the proof more interesting rather than less.

Number

Numbers that are their own parts

Six is one plus two plus three. Twenty-eight is one plus two plus four plus seven plus fourteen. Euclid explained where such numbers come from; Euler proved there are no others of that kind; and whether an odd one exists has been open for two thousand years.

Number

The sieve that cannot finish

Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.

Number

The sieve written as a product

Multiply out one geometric series for each prime and every whole number appears exactly once, as a single term. That identity turns a statement about factorisation into a statement about convergence, and it is where the analytic study of the primes begins.

Number

The size of a number with no formula

There is no closed expression for the number of partitions of n. There is an expression for how large it is — with a square root in the exponent and a π in front — and it is accurate enough that rounding a few terms of its refinement gives the exact count.

Number

The two supplements, and where the eight comes from

The main law relates two odd primes to each other and says nothing about −1 or about 2. Those two are settled separately, by their own counts, and the answers arrive modulo four and modulo eight — which is a clue about where the whole subject is really taking place.

Number

Which infinitudes are proved

The primes never stop, and neither — apparently — do the twin pairs, the primes one more than a square, or the Mersenne primes. Three of those four statements are theorems and one is not, and counting the members of each family tells nobody which.

The whole library · What the figures prove