Prime factorisation
Named by 9 essays across one field — each of them below, with the objects they name alongside it.
How many primes a typical number has
A typical number near N has about log log N different prime factors, and the count is spread around that in a bell curve whose variance is log log N as well. Both facts are theorems. Neither is visible at any size anyone can count: up to ten million the average is right and the spread is less than half what the limit says.
Euclid'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.
The same bell on thinner sets
A typical whole number has about log log N prime factors, spread in a bell curve. That was a theorem about all numbers, built on the picture of each prime dividing independently. The numbers one less than a prime, and the numbers n² + 1, are far too thin for that picture to have any obvious claim on them, and on both the same bell appears — with means shifted by constants that come straight from how often each small prime divides them. The squares plus one that are prime, the case of a single factor, number 102,205 up to n = two million against 102,302 predicted; whether there are infinitely many is open.
The largest prime in a typical number
Count a number's prime factors and the answer is about log log n. Ask instead how big the largest one is, and the answer is a power of n with a law of its own: half of all large numbers have a prime factor above n^0.6065, and the share whose primes all stay below n^(1/u) is Dickman's ρ(u), a function defined by its own past. The same law governs the longest cycle of a random shuffle, and there it arrives at once; for the numbers themselves, at ten million, it is still visibly on its way.
Two neighbours share out their small primes
A number and the next one have no prime in common, and the natural guess is that their largest primes are independent. In the limit that is believed and nearly proved. Below ten million it is visibly false: neighbours are both made of small primes only nine-tenths as often as independence predicts, a run of four only two-thirds as often, and the correlation between their largest primes is negative at distance one and positive at distance six — because a small prime that divides one of two neighbours is a small prime the other cannot have.
The product raised to the twenty-fourth power
Euler's product (1 − q)(1 − q²)(1 − q³)… has the partition numbers for its reciprocal. Raise it to the twenty-fourth power and multiply by q, and the coefficients that come out — 1, −24, 252, −1472, 4830, −6048 — multiply like the primes they are indexed by, stay inside a bound Ramanujan guessed and Deligne proved fifty-eight years later, agree with a divisor sum modulo 691, and know, modulo 23, how a cubic equation factors.
Most numbers are missing from the table
An N × N multiplication table has N² cells, and every product in it is less than or equal to N². Yet only 22.5% of the numbers that small turn up in the 10,000 × 10,000 table, and the share keeps falling. Erdős proved in 1955 that it falls to nought; Kevin Ford found in 2008 how slowly — like a tiny power of the logarithm, 0.0861 — because a product of two numbers has too many prime factors to be typical.
Divisors that take a prime whole
Six is perfect because its proper divisors 1, 2 and 3 add up to 6. Keep only the divisors that take each prime of a number completely or not at all — for 60, that is 1, 3, 4, 5, 12, 15 and 20 — and ask for the same coincidence. Below ten million it happens four times: 6, 60, 90 and 87,360. The fifth has twenty-four digits. And unlike ordinary perfect numbers, where nobody knows whether an odd one exists, here a two-line argument rules every odd number out.
The fewest ones that build a number
Build a number from ones using only addition, multiplication and brackets, and ask for the fewest ones. Six needs five, as (1+1)·(1+1+1); seven needs six. A power of three needs exactly three ones per factor, and no number does better for its size; building from binary digits never needs more than three ones per doubling. Between those bounds, the cheapest expressions are found by multiplying cheap factors and adding one. Every prime up to thirty thousand costs exactly one more than the number before it — a pattern that holds until 353,942,783.
Named alongside it
The objects these essays reach for when they reach for this one.
SieveDivisor functionExhaustive searchPrimesLargest prime factorMertens constantMultiplicative functionNormal orderSmooth numberAsymptoticsCentral limit theoremCongruence