Two neighbours share out their small primes

The largest prime in a typical number found that a number’s biggest prime factor follows a law of its own. Write $P(n)$ for the largest prime dividing $n$ and measure it as a power of $n$, $t(n) = \log P(n)/\log n$. Then the share of numbers with $t \le 1/u$ — numbers whose every prime factor is at most the $u$-th root of the number — tends to Dickman’s $\rho(u)$: about 31% have no prime factor above their square root, 4.9% none above their cube root.

That essay ended by asking about two numbers at once. A number $n$ and its neighbour $n + 1$ have no prime factor in common, since any common factor would divide their difference, which is 1. Nothing in arithmetic seems to tie the factorisation of one to the factorisation of the other, and the natural guess is that $t(n)$ and $t(n + 1)$ are independent: that the chance both neighbours are square-root smooth is $\rho(2)^2 \approx 0.094$, the chance that $n + 1$ has the larger largest prime is a half, and so on.

The guess is believed to be right in the limit. Below ten million — which is as far as a computation that looks at every single number can comfortably go — it is wrong in a way that is easy to see and easy to explain.

The corner nobody can reach #

The most striking cell in the figure is the black one at the top right. A pair lands there when both $n$ and $n + 1$ have their largest prime within a few per cent of the whole number — when both are prime, or both very nearly so. Independence, combining the two margins, predicts 44,149 pairs in that cell. There are none.

The reason is the oldest fact about neighbours: one of them is even. An even number is at most half prime — its largest prime factor is at most $n/2$, so $t(n) \le \log(n/2)/\log n$, which at ten million is 0.957. Two consecutive numbers can both be prime only if they are 2 and 3. So the corner is not merely thin but empty, and it is the first sign that the two halves of the pair are not drawn independently. Each of them is drawn from Dickman’s law, and the pair is drawn under a constraint the law knows nothing about: between them, $n$ and $n + 1$ contain exactly one factor of 2.

The rest of the figure says the same thing in a quieter voice. The blue block at the lower left, where both numbers are smooth, holds as little as a quarter of its independent share. The red strips along the edges, where one number is smooth and the other has a large prime, hold more than their share. Smoothness and roughness are being shared out between the neighbours, rather than handed to each separately.

Both smooth, less often than chance #

The cleanest measurement divides the share of numbers whose neighbour is also smooth by the square of the share of smooth numbers. If smoothness were independent between neighbours, the ratio would be one. Below ten million it is 0.91 for square-root smoothness, 0.61 for cube-root smoothness and 0.26 for fourth-root smoothness. Asking for smaller primes makes the shortfall larger, because a number whose largest prime is below its fourth root needs a great many small prime factors, and its neighbour is forbidden every one of them.

The mechanism is simple enough to put in a sentence. A number is smooth by being divisible by many small primes; each small prime $p$ divides one number in $p$, but never two consecutive numbers, so if $n$ has used up its share of 2s, 3s and 5s, $n + 1$ is guaranteed to have none of them and must build itself from larger primes. Two independent numbers can both be divisible by 2, 3 and 5; two neighbours cannot.

The ratio for square-root smoothness rises steadily — 0.58 at a thousand, 0.73 at ten thousand, 0.82 at a hundred thousand, 0.88 at a million, 0.91 at ten million — and that is the behaviour independence in the limit predicts. As numbers grow, the small primes become a smaller part of every number’s logarithm, and how they are shared out matters less and less to where the largest prime lands. The convergence is slow, like an inverse power of $\log x$, which is why ten million is still visibly short of it. The same slowness made the bell curve of prime factors narrower than its theorem at every size anyone can count: statements about the factorisation of a typical number are true at sizes that grow like exponentials of exponentials, and any table is a snapshot from the foothills.

Which neighbour has the larger prime #

Some statistics of the pair are symmetric and ignore the sharing out. Whether $P(n) < P(n + 1)$ or the reverse is one of them: whatever constraint links the neighbours, it treats $n$ and $n + 1$ alike, so the larger prime should belong to each half the time. The plain share is 0.5000 at ten million. The share weighted by $1/n$, which leans on small numbers, is still 0.519, because among very small numbers the larger number tends to have the larger prime.

Even this needed a theorem. Paul Erdős and Carl Pomerance asked in 1978 for a proof that the share is a half, and could prove only that each order occurs a positive proportion of the time. Joni Teräväinen proved in 2018 that the weighted share tends to a half, building on Kaisa Matomäki and Maksym Radziwiłł’s work on multiplicative functions in short intervals and Terence Tao’s on their correlations. Whether the plain, unweighted share tends to a half is still open. The weighted share is the easier target for the same reason it converges more slowly: weighting by $1/n$ averages over all scales at once, and the tools for multiplicative functions are better at averages over scales than at single long stretches.

The correlation follows the small primes #

The sharing-out argument predicts more than a negative correlation between neighbours; it predicts how the correlation should change with the distance. Two numbers a distance $k$ apart can both be divisible by a prime $p$ exactly when $p$ divides $k$. At distance 1 they share nothing, and the correlation is the most negative of all, $-0.060$. At distance 6 they can both be divisible by 2 and by 3, the two primes that matter most, and the correlation turns positive, $+0.007$; at distance 12, with 4 and 3 in common, it is $+0.023$. Distances that share only one of 2 and 3 sit between: $-0.028$ at 2, $-0.025$ at 3, $-0.012$ at 4, $-0.013$ at 9. The distances coprime to 6 — 1, 5, 7 and 11 — are all among the most negative, at $-0.06$, $-0.026$, $-0.028$ and $-0.032$.

So the correlation is not a property of nearness at all. It is a property of shared divisibility, and nearness matters only because nearby numbers have small differences, which have few prime factors. This is the same structure that makes Euclid’s numbers coprime to every prime on their list and that runs through every sieve, including the one written as a product over primes: the residues of $n$ modulo small primes are independent, and the residues of $n$ and $n + k$ modulo $p$ are tied together exactly when $p$ divides $k$.

Neighbours built from small primes only #

The extreme case of sharing out is the case where both neighbours are smooth with respect to a fixed bound — not a root of the number, but a fixed set of primes.

Carl Størmer proved in 1897 that for any finite set of primes there are only finitely many pairs of consecutive numbers built from those primes alone. With primes up to 3 there are four pairs, the last being 8 and 9; up to 5, ten, ending at 80 and 81; up to 7, twenty-three, ending at 4,374 and 4,375, which are $2 \cdot 3^7$ and $5^4 \cdot 7$; up to 11, forty, ending at 9,800 and 9,801; up to 13, sixty-eight, ending at 123,200 and 123,201. A search below ten million finds no more, and it does not need to look further: D. H. Lehmer turned Størmer’s method into an algorithm in 1964 and listed the pairs completely for every bound up to 41, and the lists agree.

The method is the one that solves Pell’s equation. If $n$ and $n + 1$ are both built from a fixed set of primes, write $n(n + 1)$ as $D y^2$ with $D$ squarefree and built from the same primes — finitely many choices — and then $(2n + 1)^2 - 4 D y^2 = 1$, a Pell equation. Each Pell equation has one fundamental solution that generates all the others, and Størmer showed that a consecutive smooth pair can only come from the fundamental solution or very near it, so each $D$ contributes at most a few pairs. Finitely many $D$, finitely many pairs.

There is a famous special case. With only the primes 2 and 3, the pair 8, 9 is a power of 2 next to a power of 3, and Eugène Catalan conjectured in 1844 that it is the only pair of consecutive perfect powers of any kind. Preda Mihăilescu proved it in 2002. Størmer’s theorem is the version where the primes are fixed and the exponents are free; Catalan’s is the version where the exponents are at least two and the primes are free; both say that consecutive numbers resist sharing their structure, and both are about as far from independence as two numbers can be.

Runs get rarer faster than chance #

The sharing argument compounds over longer runs. A run of three consecutive square-root smooth numbers needs three numbers that between them contain one or two factors of 2, one factor of 3 at most, and so on, and each must be smooth with what the others leave. The measured rates fall further below independence with each extra number: 0.91 for pairs, 0.80 for triples and 0.67 for runs of four. The first run of three square-root smooth numbers begins at 48 — 48, 49 and 50 — and the first run of four at 1,518.

The same accounting explains a fact that looks like a coincidence in the first figure: the strips where one neighbour is smooth and the other rough are over-filled. If the small primes have gone to $n$, then $n + 1$ is coprime to all of them, and a number coprime to every small prime is more likely than a typical number to have a large prime factor. Sharing out does not destroy smoothness; it moves it from one neighbour to the other.

Why factoring cares about smooth neighbours #

Smooth numbers are not a curiosity. The fastest general methods for factoring a large number $N$ — the quadratic sieve and the number field sieve — work by finding many numbers that are smooth and whose product is a square modulo $N$. The quadratic sieve looks at $x^2 - N$ for $x$ just above $\sqrt N$, a run of values that are roughly consecutive in size, and keeps the smooth ones. That it can find them fast is the sieve’s whole trick: a prime $p$ divides $x^2 - N$ for $x$ in two fixed residue classes modulo $p$, so the values it divides recur with period $p$, and they can be marked without trying a single division — exactly the periodicity that ties $n$ and $n + k$ together when $p$ divides $k$.

The sharing out measured here is the same phenomenon seen from the other side. When a sieve marks every $p$-th value, it never marks two values closer together than $p$ — at least not for the same residue class — so smooth values come with a definite spacing rather than at random, and the sieve’s yield is governed by how the small primes are distributed across the run, which is a question about correlations of the kind in the figure above. The running time of the quadratic sieve, $\exp\big((1 + o(1))\sqrt{\ln N \ln\ln N}\big)$, is computed from Dickman’s law as though the values were independent, and it is right to leading order for the reason the ratios above approach one: at the sizes that matter for factoring, the small primes are a vanishing part of each number.

Other factoring methods meet smoothness differently. Pollard’s rho method needs no smoothness at all and finds a factor by a collision; his $p - 1$ method finds a prime $p$ exactly when $p - 1$ is smooth, so it succeeds or fails according to the factorisation of the neighbour of the prime it is looking for. Every one of these methods rests on the uniqueness of factorisation, and every one is limited by how rarely numbers of a given size are made of small primes.

Consecutive smooth numbers and the abc question #

Størmer’s pairs have a second life. If $n$ and $n + 1$ are both made of small primes, then $1 + n = n + 1$ is an equation $a + b = c$ in which $a$, $b$ and $c$ have no common factor and the product of the distinct primes dividing $abc$ — the radical — is small compared with $c$. For 4,374 and 4,375 the radical is $2 \cdot 3 \cdot 5 \cdot 7 = 210$, against $c = 4{,}375$; for 123,200 and 123,201 it is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30{,}030$, against $c = 123{,}201$.

The abc conjecture of Joseph Oesterlé and David Masser says that the radical cannot be much smaller than $c$: for every $\varepsilon > 0$, only finitely many such equations have $c > \text{rad}(abc)^{1 + \varepsilon}$. Størmer’s theorem is the special case where the primes are fixed in advance and the equation is $1 + n = n + 1$; the conjecture would extend it to every set of primes at once, with a bound on how large the last pair can be. Whether it is true is disputed in a way that is unusual in mathematics — a claimed proof from 2012 has not been accepted by most of the specialists who have examined it — and the computational evidence, from searches for equations with small radicals, supports it.

What the computations assume #

Every number here was found by a sieve that writes, for each $n$ up to ten million and twelve beyond, its largest prime factor. Nothing in the figures is asymptotic: the ratios are what they are at ten million, and the claim that they tend to one rests on the slow growth already visible and on the heuristic that small primes matter less as numbers grow, not on anything proved. The Størmer lists are complete because Lehmer proved them complete, not because the search stopped at ten million.

The correlations are small — the largest is six hundredths — and they are measured over ten million pairs, so their standard errors are a few ten-thousandths and every one of the twelve is real. Real and small are both worth saying. A model of the factorisations of $n$ and $n + 1$ as independent Dickman variables is an excellent model for most purposes at these sizes; it is wrong in a specific, explainable direction, and the explanation says when it will stop being wrong.

Still open: independence in the limit #

Do the largest prime factors of $n$ and $n + 1$ become independent? The conjecture is that the pair $(t(n), t(n + 1))$ has, in the limit, the joint law of two independent Dickman variables, so that, for instance, both neighbours are square-root smooth for a share $\rho(2)^2 \approx 0.094$ of $n$. It is not known even that this share exists. Lower bounds showing that smooth neighbours, and longer strings of smooth numbers, occur with positive frequency have been proved for various levels of smoothness, by Adolf Hildebrand and by Antal Balog and Trevor Wooley among others; but no one has shown that the share has a limit, let alone that the limit is $\rho(2)^2$. The recent methods that settled the logarithmic version of the ordering question are, so far, much better at symmetric questions than at quantitative ones. The question is a two-point version of the large questions of multiplicative number theory, of the same family as whether the bell of prime factors survives on thinner sets, and it is a fair guess that it will be settled by the same tools when they are strong enough.

One prime cannot divide two neighbours #

A number and its neighbour share no prime, and that one fact pulls their factorisations apart. Below ten million the corner where both are prime is empty, both are square-root smooth only 0.91 times as often as independence predicts and fourth-root smooth 0.26 times, runs of smooth neighbours fall further below chance as they lengthen, and the correlation between largest primes is negative at distance one and positive at distance six, following exactly the small primes the distance can share. The shortfalls shrink as numbers grow, as independence in the limit requires, and the symmetric question of which neighbour has the larger prime already sits at a half.