Concept

Prime factorisation

The expression of a whole number greater than one as a product of primes, which is unique apart from the order of the factors. Finding it is easy to state and slow to do for large numbers, and its uniqueness is what lets a number be read off from its primes.

Named by 9 essays across one field — each of them below, with the objects they name alongside it.

How many different primes divide a number up to ten million. The share of numbers up to 10⁷ with each count of distinct prime factors (6.7%, 25.4%, 36.4%, 23.9%, 6.9%, 0.7%, 0.0%, 0.0%), against the Erdős–Kac normal curve with mean and variance 2.78.

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.

number · Unique factorisation
Euclid's argument run twenty times. The first 20 terms of the Euclid–Mullin sequence: 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957.

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.

number · Infinitude of primes
The same bell on numbers, on primes less one, and on squares plus one. Standardised ω histograms: integers ≤ 2·10^7, p − 1 for p ≤ 2·10^7, n² + 1 for n ≤ 2·10^6.

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.

number · Unique factorisation
The largest prime factor, as a power of the number. Share of n with log P(n)/log n ≤ s: at s=0.5, n≤10⁴ 0.268, n≤10⁷ 0.272, Dickman 0.307; median e^(−1/2) = 0.6065; largest gap at 10⁷ 0.061.

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.

number · Unique factorisation
The largest primes of n and n + 1, side by side. Joint law of t(n), t(n+1) for 1000≤n<1e7 in 24×24 cells: corner (both near prime) 0 against 44149 expected; other ratios 0.268 to 2.582.

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.

number · Unique factorisation
Ramanujan's tau, scaled by the power it grows like. τ(n)/n^5.5 for n ≤ 400; τ(1..8) = 1, -24, 252, -1472, 4830, -6048, -16744, 84480; largest |τ(n)|/n^5.5 for n ≤ 10000: 3.2796 at 4841.

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.

number · Partitions
A multiplication table and its repeats. n=30: 308 distinct products of 900.

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.

number · Unique factorisation
The unitary divisors of every number, and the four that sum to exactly twice. sigma*(n)/n for n up to 100000; equal to 2 at 6, 60, 90, 87360; maximum 3.2224 at 30030. Search to 10000000 finds 6, 60, 90, 87360.

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.

number · Perfect numbers
The fewest ones that build a number. 10:7 100:14 1000:21 1439:26 2000:23

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.

number · Unique factorisation

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

All concepts