The sieve of Eratosthenes below 100
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.
With nothing chosen
Each prime fixes the next digits of A
The chain of primes behind Mills' constant
A truncated constant returns what it holds
The cube windows are almost empty of need
The square windows, where no theorem reaches
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 narrowest admissible 2-tuple has width 2 ×9
- 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
- (0, 2, 4) is not admissible: one of three numbers two apart is a multiple of 3 ×1
- a Mersenne prime has a prime exponent ×1
- a narrowest admissible pattern is found ×1
- a pattern is admissible exactly when it leaves a remainder free mod every prime ×1
- a small prime works for every even number in range ×1
- a square left unstruck holds a prime, and a struck one does not ×1
- a truncated constant recovers more primes as it carries more digits ×1
- after small cases the first odd number that is not a prime plus a power of two is 127 ×1
- after the fifth term the largest-factor sequence never returns below fifty thousand in the terms computed ×1
- an earlier term leaves remainder 1 ×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 sifting the odd half leaves exactly the primes above √x ×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
- and thirty is favoured over its neighbours ×1
- between two and five odd primes are listed ×1
- both classes hold primes below the bound ×1
- both ends are prime ×1
- Chen's primes greatly outnumber the twins ×1
- each is near the share an even split would give ×1
- each prime in the chain fixes about three times as many digits of A as the last ×1
- each prime lies below the next cube ×1
- every class coprime to the modulus holds primes ×1
- every count is within fifteen per cent of its prediction ×1
- every exponent has at least one prime dividing it ×1
- every interval from n to 2n holds a prime ×1
- every number strictly between is composite ×1
- every pair count is within eight per cent of Hardy and Littlewood's prediction ×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
- every record so far sits below (log p)² with room ×1
- every window between consecutive powers holds a prime ×1
- gaps of six outnumber gaps of two and four in this range ×1
- Ingham's exponent already allows the power 3, and the best known allows any power above 2.106 ×1
- Mertens' product is within two per cent of e^γ ln p at 1,100 ×1
- multiplying the factors out gives exactly the sum over the numbers they build ×1
- no listed prime divides it ×1
- no record below thirty million reaches (log p)² ×1
- one gap between each consecutive pair ×1
- seventy-one composites in a row ×1
- sifting the even half by every prime below √x leaves nothing ×1
- the bound the postulate is checked to is a whole number between 100 and 50000 ×1
- the chain agrees with the published one ×1
- the column count is a whole number between 4 and 25 ×1
- the constant agrees with the published value ×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 coverings drawn are those of 78557 and 271129 ×1
- the factorisation multiplies back to the number built ×1
- the factors are between 2 and 4 primes ×1
- the five classes cover every whole number ×1
- the full inclusion-exclusion agrees with the count made by sifting ×1
- the gap of 210 first appears after 20,831,323 ×1
- the gap of 72 first appears after 31,397 ×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 n up to 170 with n! + 1 prime are the known list ×1
- the n up to 170 with n! − 1 prime are the known list ×1
- the next term divides the number ×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 option is one this view reads ×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 primes p up to 1,100 with p# + 1 prime are the known list ×1
- the primes p up to 1,100 with p# − 1 prime are the known list ×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 residue method's factor divides p# + 1 ×1
- the sieve finds the 1,857,859 primes below thirty million ×1
- the sieve found every prime below the bound ×1
- the smallest factor of p# + 1 exceeds p ×1
- the smallest factor of p# − 1 exceeds p ×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 test finds the known exponents for 3·2ⁿ + 1 ×1
- the two halves' shares of multiples of every d agree to within a fifth ×1
- the view is one the family draws ×1
- there are 25 primes below 100 ×1
- up to this bound the sum never rises above zero after n = 1 ×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
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 constant that holds the primes
There is a number A = 1.3063778838… such that A cubed, A to the ninth, A to the twenty-seventh and every further power of three, rounded down, is prime: 2, 11, 1361, 2521008887 and on for ever. W. H. Mills proved in 1947 that such a number exists. It looks like a formula for primes and is the opposite of one. Its digits are read off the primes it produces, each prime fixes about as many digits as it has, and the whole argument stands on a theorem about gaps between primes — which is why the power is 3 and not 2.
NumberAlways 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.
NumberCounting 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.
NumberThe 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.
NumberEuclid's proof run as a machine
Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.
NumberEvery 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.
NumberInfinitely 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.
NumberThere 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.
NumberNumbers 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.
NumberNumbers that never make a prime
Multiply 78,557 by a power of two and add one. The result is never prime, for any power, though almost every other odd number gives a prime within a few doublings. The reason is that seven small primes take it in turn to divide the result, on a schedule repeating every 36 steps that leaves no step uncovered. Proving nothing smaller does this has taken sixty years of search, and five candidates are still running.
NumberThe comet Goldbach left behind
Count the ways each even number is a sum of two primes, and the points do not form a smear. They split into bands: 12,000 has 302 ways and 12,002 has 115. One small product over odd prime factors explains every band and brings them all to a single line, and it says the count grows without bound. Nobody can prove the count is never nought.
DiscreteThe longest wait for a prime
Near a number x the primes are on average log x apart, and the longest stretch without one below x is much longer: about the square of log x, if the primes behave like random numbers with the right density. Sieving to thirty million finds twenty-four record gaps, all climbing in the shape of that square and all below it. A random model of the primes gets the scale right and the details wrong, and the correction for what it gets wrong predicts gaps larger still — larger than any anyone has found.
NumberThe patterns primes are allowed to make
Primes two apart are twin primes; primes six apart are about twice as common; three primes two apart happen exactly once, at 3, 5, 7. Which patterns of primes can recur for ever is decided by remainders alone — a pattern must leave some remainder free modulo every prime — and how often each one recurs is predicted, to within a few per cent, by a constant computed from nothing else.
NumberThe 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.
NumberThe 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.
NumberThe 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.
NumberThe 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.
NumberTwo halves a sieve cannot tell apart
Split the whole numbers into those with an even number of prime factors and those with an odd number. To a sieve — which sees only how many numbers each small divisor divides — the two halves look almost exactly alike. Yet sifting out the small primes leaves every prime in one half and nothing at all in the other. That is Atle Selberg's parity example, and it is the reason no sieve can prove there are infinitely many twin primes.
NumberWhen Euclid's number is itself prime
Multiply the primes up to p and add one. Euclid needed only that the result has a prime factor beyond p; it is itself prime for p = 2, 3, 5, 7 and 11, and then not again until 31, and then not until 379. Up to 1,100 there are nine such primes of each sign, against thirteen that a careful estimate expects. The estimate predicts infinitely many and grows by about 1.8 every time x is multiplied by e; nobody can prove there is even one more.
NumberWhich 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.