The largest prime in a typical number

How many primes a typical number has counted. A number near $N$ has about $\log \log N$ different prime factors, spread around that in a bell curve whose variance is $\log \log N$ as well, and the same bell on thinner sets found the same count, slightly shifted, on the numbers one less than a prime and on the squares plus one. Both essays treated the prime factors as a list to be counted, each small prime dividing independently with probability one over itself, like a coin. That picture said nothing about how large the factors are, and it could not, because for the count the large primes hardly matter: a number can have at most one prime factor above its own square root.

But the large primes are where most of a number’s size is. Of the digits of a typical number near a million, more than half belong to its largest prime factor. The question this essay measures is how large that factor is — not in absolute terms, which grow with the number, but as a power of it. The answer is a law, found by Karl Dickman in 1930, governed by a function that is defined by its own past and has no closed form beyond its first piece. It also governs, exactly and by a different route, the longest cycle of a shuffled pack of cards.

A number’s largest prime, measured as a power #

Write $P(n)$ for the largest prime dividing $n$. For a prime, $P(n) = n$; for a power of two, $P(n) = 2$. The ratio $s = \log P(n) / \log n$ puts every number on the same scale: $s = 1$ for primes, $s = 1/2$ for the square of a prime and for a number whose largest prime is about its square root, and $s$ near zero for numbers built entirely from small primes. The hero figure computes $P(n)$ for every $n$ up to ten million — by a sieve that walks through the multiples of each prime in increasing order and writes the prime into each, so that the last prime written is the largest — and plots the share of numbers whose $s$ is at most each value.

The curve has a shape that the counting essays gave no hint of. Almost no number has $s$ below $0.2$: a number whose prime factors are all below its fifth root is rare. Among the numbers up to ten million, a fifth have $s$ below $0.47$, a quarter below about $0.49$, and half below about $0.63$. Above that the curve climbs steadily to the right-hand edge, where it jumps: the jump is the primes, every one of which has $s = 1$, and there are about $n / \log n$ of them, a share that shrinks as the range grows. Dickman’s theorem says that this curve has a limit. As the range grows, the share of $n$ with $s \le t$ tends to $\rho(1/t)$, where $\rho$ is a function he defined for the purpose, and the median of the limit is exactly $e^{-1/2} = 0.6065$: half of all large numbers have a prime factor larger than $n^{0.6065}$.

The counted curves lie below the limit, and the gap is closing. At ten thousand the largest gap is about twelve percentage points; at ten million it is about six. The direction of the gap means that at these sizes the largest prime factor is a slightly bigger power of the number than the limit allows — a small-number effect that the second figure below and the fourth will trace.

A function defined by its own past #

The heuristic behind Dickman’s function is a self-similarity. Suppose a number $n$ has its largest prime $p$ of size about $n^{1/v}$ for some $v$. Then $n = p \cdot m$, where $m$ is about $n^{1 - 1/v}$, and $m$’s own prime factors are all at most $p$. Asking for the share of $n$ whose primes are all below $n^{1/u}$ thus turns into an average, over the possible sizes of the largest prime, of the same question asked about a smaller number with a smaller exponent. Written as a calculus statement, the share $\rho(u)$ of numbers whose prime factors are all at most $n^{1/u}$ satisfies

$$u \, \rho'(u) = -\rho(u - 1), \qquad \rho(u) = 1 \text{ for } 0 \le u \le 1.$$

The equation is a delay differential equation: the slope at $u$ depends on the value one unit back.

The first piece can be found by hand. For $u$ between 1 and 2, the value one unit back is 1, so $u\rho'(u) = -1$, and $\rho(u) = 1 - \log u$. At $u = 2$ this gives $\rho(2) = 1 - \log 2 = 0.3069$: the share of numbers with no prime factor above their square root is about 31 per cent, and so the share with one prime factor above its square root — there can be only one — is about 69 per cent. On the next interval the value one unit back is $1 - \log(u - 1)$, and the integral that results involves the dilogarithm; after that the pieces are new functions each time, and nothing simpler than the equation itself describes them. The figure computes $\rho$ by integrating the equation one unit interval at a time, using the interval before as known input. The one care needed is at the integers, where each derivative in turn has a kink: a numerical rule that averages across a kink loses accuracy there, and a first attempt that did so drifted by a few parts in a billion — invisible on this figure, and a factor of a hundred on the logarithmic scale of the last one. Restarting the rule at every integer removes the drift.

Smooth numbers, and how slowly the limit arrives #

A number whose prime factors are all at most $y$ is called $y$-smooth, and the count of $y$-smooth numbers up to $x$ is written $\Psi(x, y)$. Dickman’s theorem in this form says that for every fixed $u$,

$$\Psi\bigl(x, x^{1/u}\bigr) \sim x\,\rho(u) \qquad \text{as } x \to \infty.$$

This is a statement about a fixed bound $x^{1/u}$ for all numbers up to $x$, rather than a bound that moves with each $n$ as in the hero figure, and it is the form used everywhere smooth numbers matter.

The counts confirm the theorem’s direction and expose its pace. Every ratio is above 1 and falls at every tenfold step, as it must if it is to reach 1. For $u = 2$ it has nearly arrived: there are 3,362,157 numbers up to ten million with no prime factor above $\sqrt{10^7} \approx 3{,}162$, against a prediction of 3,068,528, ten per cent more. For $u = 5$ it has barely started. The bound is then $10^{7/5} \approx 25.1$, so the count is of numbers built entirely from the nine primes up to 23, and there are 28,434 of them against a prediction of 3,547. Dickman’s theorem fixes $u$ and lets $x$ grow, so the bound $x^{1/u}$ grows too, and the limit describes numbers whose smoothness bound is itself large. At ten million and $u = 5$ the bound is 25, and a set of nine primes is nothing like the limiting picture of primes thick enough to be treated as a continuum.

The correction is known in principle — Nicolaas de Bruijn gave an asymptotic expansion in 1951, and Adolf Hildebrand determined in 1986 how small $y$ can be, relative to $x$, for the approximation by $\rho$ to remain good — but the practical lesson of the figure is simpler. The approximation is good when the smoothness bound has many primes below it and poor when it has few, and at the sizes anyone can count, “few” covers most of the interesting range.

The average largest prime #

Integrating Dickman’s law gives the average of $s = \log P / \log n$ over all large numbers:

$$\lambda = \int_0^1 \bigl(1 - \rho(1/t)\bigr)\, dt = 0.62433\ldots$$

This is the Golomb–Dickman constant. On average, the largest prime factor of a large number accounts for about 62 per cent of its digits.

The counted mean is $0.6572$ for numbers up to a thousand and $0.6466$ for numbers up to ten million — still two and a quarter hundredths above the limit, after multiplying the range by ten thousand. The median, read to the nearest half-hundredth, falls from $0.650$ to $0.630$ against $0.6065$. The pace is the same slow pace as for the smooth counts, and the figure measures it. It is far slower than the pace at which the bell arrives for a sum of independent terms, where the error falls like one over the square root of the number of terms; here the number of terms is in effect $\log x$, and the error falls like its reciprocal. If the excess of the mean over $\lambda$ were shrinking like a constant divided by $\log x$, then multiplying it by $\log x$ would give a sequence levelling off at that constant; the products are $0.23$, $0.28$, $0.32$, $0.35$ and $0.36$, rising more slowly at each step. The excess at ten million is about $0.36/\log x$, and if the constant settles near $0.4$, closing the excess to one hundredth would take $x$ of about $10^{17}$.

That rate has a plain cause. The smallest primes, 2 and 3 and 5, are fixed while $\log x$ grows, and they are the ones whose contribution to $\log n$ the limit treats as negligible. A number up to a thousand that is $2 \times$ a prime has $s$ close to 0.9, and there are many of them; in the limit, the factor 2 is a vanishing part of $\log n$, and $s$ for such numbers tends to 1 — but also, in the limit, almost no number is twice a prime. The finite ranges carry the memory of their small primes in every statistic, and that memory fades like $1/\log x$.

A shuffle obeys the same law, and obeys it sooner #

Solomon Golomb met the constant $0.62433$ in 1964 in a problem that has nothing to do with primes: the longest cycle of a random permutation. Shuffle $n$ cards, follow where the card in position 1 goes, then where that card’s position goes, and so on until the path returns to position 1; that is a cycle, and the shuffle breaks the cards into cycles. Golomb asked for the expected length of the longest one, as a fraction of $n$, and found it tends to $0.62433$. Lawrence Shepp and Stuart Lloyd showed in 1966 that the whole distribution of the longest cycle’s share tends to Dickman’s law, and later work showed that the agreement is complete: the sizes of all the cycles, as fractions of $n$, and the sizes of all the prime factors, as fractions of $\log n$, follow the same limiting law, the Poisson–Dirichlet distribution.

For shuffles the law can be computed exactly at every $n$. If $p_m(n)$ is the chance that a random permutation of $n$ objects has every cycle of length at most $m$, then the cycle containing the first object has each length from 1 to $n$ with equal probability $1/n$, and what remains is a random permutation of the other objects, so

$$p_m(n) = \frac{1}{n} \sum_{k=1}^{\min(m, n)} p_m(n - k).$$

The figure computes this for ten, thirty and a hundred objects and draws the resulting staircases against Dickman’s curve. At a hundred objects the steps already sit on the curve: the chance of no cycle longer than fifty is $0.3118$, within half a percentage point of $1 - \log 2$. The convergence is fast — the error shrinks like $1/n$ — because a permutation has no analogue of the small primes. The same is true at the other end of the cycle structure: how many get their own hat counted the cycles of length one, the objects a shuffle leaves where they were, and found their number settling on its limiting law almost immediately. Every cycle length from 1 to $n$ is equally available to the first object, and the first object is a uniform sample of the whole.

So the same function appears in two places with different speeds. Shuffles reach it within a hundred cards. Integers have not reached it by ten million, because the role $n$ plays for shuffles is played for integers by $\log n$ — ten million has a logarithm of only sixteen — and because the integers’ small primes give the finite picture a bias that a shuffle does not have. The comparison is the clearest evidence of what $\rho$ describes: not something about primes in particular, but about breaking a whole into pieces at random, one piece at a time, each a uniform share of what remains. A perfect coin and a biased shuffle followed what goes wrong when a shuffle is not uniform; Dickman’s law is what a uniform one looks like from the inside.

How rare smoothness gets #

For large $u$, Dickman’s function falls faster than any exponential. Roughly, $\rho(u)$ is about $u^{-u}$; more precisely, $\log \rho(u) = -u(\log u + \log \log u - 1 + o(1))$, a form de Bruijn gave.

The values matter in computation, because smooth numbers are the raw material of every fast method for factoring large integers. Pollard’s $p - 1$ method finds a prime factor $p$ quickly when $p - 1$ is smooth. A collision that finds a factor followed Pollard’s other method, whose speed is set by the birthday problem rather than by smoothness, and which for that reason is slower on the largest numbers. The quadratic sieve and the number field sieve, which hold the records for factoring numbers of no special form, work by finding many numbers in a structured sequence that are smooth, and then combining them; the expected number of tries is $1/\rho(u)$ for the appropriate $u$, and the whole art of those methods is choosing sequences whose members are small, so that $u$ is small, while keeping enough structure to combine them. Hendrik Lenstra’s elliptic curve method of 1987 replaces $p - 1$ by the size of a random group near $p$, and its running time is again an expression in $\rho$.

The figure’s numbers make the stakes concrete. The chance that a random 60-digit number has no prime factor above a million is $\rho(10) = 2.77 \times 10^{-11}$. The counted points at ten million show again why the limit must be used with care: for $u = 7$, the bound $10^{7/7}$ is 10, and the numbers counted are those made only of 2, 3, 5 and 7, of which there are far more than $\rho(7)$ predicts — 2,155 in ten million against about nine. Analyses of factoring algorithms use $\rho$ at sizes where the bound has thousands or millions of primes below it, and there the limit is accurate; the figure shows the region where it is not.

What the size of the largest prime adds #

The counting essays found that a number’s prime factors, as a list, behave like independent coins — each small prime $q$ dividing with chance $1/q$. Dickman’s law is the same independence seen from the other end. The share of numbers divisible by a prime $p$ near $n^{1/v}$, with no larger prime, can be computed from that independence, and what it gives, summed over $p$ and taken to the limit, is the delay equation. The two pictures — many small coins, one large piece — are the same probability model, read for the small primes and for the large ones. One way to factor, and no other began this sequence by saying that the factorisation of a number is unique; these last essays have found that it is also, statistically, completely predictable, from the count of its smallest pieces to the size of its largest.

There is one more connection, back to Euclid’s proof run as a machine, which took products of primes plus one and followed their factors. Keeping the largest prime factor at each step instead of the smallest gave a sequence that climbs at once into primes of many digits, passing over small primes as factors it does not keep, and Andrew Booker proved that it misses infinitely many primes. The speed of the climb is what Dickman’s law predicts for a typical number: its largest prime factor carries, on average, about 62 per cent of its digits, and a sequence that keeps only that factor discards the rest at every step.

Still open: the joint law at consecutive numbers #

Dickman’s law describes one number at a time. For two consecutive numbers $n$ and $n + 1$, the natural guess is that their largest prime factors are independent, so that, for example, the chance that both are $\sqrt{x}$-smooth is $\rho(2)^2 \approx 0.094$. Nothing contradicts this, and counts like the ones above agree with it, but it is not proved in general; even simple consequences, such as $P(n) < P(n+1)$ holding for exactly half of all $n$, have needed the strongest modern methods for correlations of multiplicative functions. The difficulty is the same one met at the end of the same bell on thinner sets: correlations between the prime factors of nearby numbers are questions about primes in short intervals and polynomial patterns, and they lie beyond the reach of sieves.

A second open question is quantitative. The smooth counts in the figures stay well above $x\rho(u)$ at every size that can be enumerated, and the better approximations to $\Psi(x, y)$ — de Bruijn’s expansion, and saddle-point methods that track the actual primes below $y$ — are accurate but not explicit in the way $\rho$ is. A practical, provable estimate that is good at the sizes cryptographers care about, with error bounds that can be stated in advance, would settle a number of security estimates that are currently made by extrapolating counts like these, and it does not yet exist.