Divisors that make every amount

The weird numbers were defined by a failure: abundant, and yet no selection of their divisors adds up to them. Their opposite is a success of the strongest kind. Take twelve. Its divisors are $1, 2, 3, 4, 6$ and $12$, and they add to $28$. Every whole number from one to twenty-eight can be made by choosing some of them, each at most once: $5 = 4 + 1$, $11 = 6 + 4 + 1$, $17 = 12 + 4 + 1$, $27 = 12 + 6 + 4 + 3 + 2$. Twelve’s divisors are a complete set of weights for every amount up to their total.

A number with this property — every amount from one up to the number itself can be made from distinct divisors, and so every amount up to their sum — is called practical. The name was given by A. K. Srinivasan in 1948, but the idea is much older. Fibonacci’s Liber Abaci of 1202 uses such numbers to break fractions into sums of unit fractions, the Egyptian way, and a merchant weighing goods with a set of weights is asking the same question about a different list of numbers.

The first practical numbers are $1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32$. Every power of two is practical — the sequence of practical numbers is, among other things, a list of the numbers that can serve as complete sets of weights — since $1, 2, 4, \ldots, 2^k$ are the binary digits and make every amount up to $2^{k+1} - 1$. Every factorial is practical. And every even perfect number is practical, which ties this question back to the perfect numbers it grew from: $2^{p-1}(2^p - 1)$ has the powers of two up to $2^{p-1}$ among its divisors, which make every amount below $2^p$, and the prime $2^p - 1$ fits exactly into the next gap.

The Egyptian use #

The reason Fibonacci cared is visible in the next figure. If $n$ is practical, then every numerator $a$ below $n$ is a sum of distinct divisors $d$ of $n$, and each fraction $d/n$ is a unit fraction $1/(n/d)$.

So $\tfrac{5}{24} = \tfrac{4}{24} + \tfrac{1}{24} = \tfrac16 + \tfrac1{24}$, and $\tfrac{23}{24} = \tfrac{12}{24} + \tfrac{8}{24} + \tfrac{3}{24} = \tfrac12 + \tfrac13 + \tfrac18$. The Egyptian scribes wrote every fraction except $\tfrac23$ as a sum of distinct unit fractions, and finding such sums was a computational skill in the ancient world and in medieval Europe. A practical denominator makes the skill mechanical: express the numerator in the divisors, read off the unit fractions. How few unit fractions a fraction needs is a much harder question — whether every $4/n$ needs at most three is the Erdős–Straus conjecture, still open — but practical denominators guarantee that some decomposition exists and can be read off. One of the methods in Fibonacci’s catalogue for a general fraction rewrites it over a practical denominator first — multiplying top and bottom by a suitable number — and then splits it this way.

That gives the property its name in reverse. A practical number is one in which every share of a whole can be paid in coins worth divisors of the whole, each coin used once. Twelve pence was practical; so was the sixty-minute hour and the 360-degree circle, and the old measures built on twelves and sixties were practical in exactly this sense.

Twelves, sixties, and the trouble with ten #

The rule explains a pattern in the units people chose before they chose decimals. Twelve is practical, and so is the twelve-hour dial; so are $16$ ounces to the pound, $24$ hours to the day, $60$ minutes to the hour, and $360$ degrees to the circle. Sixty, $2^2 \cdot 3 \cdot 5$, passes the rule with room to spare: the divisors of $4$ make up to $7$, so $3$ fits; the divisors of $12$ make up to $28$, so $5$ fits. Any whole number of minutes from one to sixty is a sum of distinct divisors of sixty, which is to say any share of an hour can be paid out in distinct “nice” fractions of an hour.

Ten is not practical. Its divisors $1, 2, 5, 10$ cannot make four: five arrives before the small divisors have built up to it. The decimal system’s base is a poor number for dividing things, which is the old complaint of the duodecimalists, and the rule says precisely what is wrong with it — the prime five comes too early for a single factor of two to support. Curiously, a hundred and a thousand are practical: $2^2$ makes up to seven, enough for five, and $2^3$ makes up to fifteen. The everyday coins of a decimal currency — $1, 2, 5, 10, 20$ and $50$ hundredths — are all divisors of a hundred, and they lean on the extra factor of two that ten lacks.

Whether the people who settled on twelves and sixties had anything like this rule in mind is not something the arithmetic can say. What it can say is that the numbers they chose have the property that makes division by small numbers painless, and that the property has an exact characterisation that they did not need to know.

A rule on the primes #

Checking whether a number is practical by trying every amount is slow for large numbers. B. M. Stewart in 1954 and Wacław Sierpiński in 1955 found that the answer can be read off the prime factorisation.

The rule builds the number one prime at a time. Start with the power of two: its divisors make every amount up to its divisor sum. Bringing in the next prime $p$ multiplies the set of divisors by $1, p, p^2, \ldots$, and the new amounts can fill in seamlessly only if $p$ is no bigger than one more than everything the earlier divisors could make — otherwise there is a gap just below $p$ that nothing reaches. For 120 the chain is $2^3$, whose divisors make up to 15; then $3 \le 16$, after which the divisors make up to 60; then $5 \le 61$. For 3024 the bound before the last prime is already 1,241, and 7 fits with room to spare.

The rule explains at a glance why odd numbers above one are never practical (the amount two cannot be made without the divisor two), why $2 \cdot 5 = 10$ is not practical ($5 > 1 + 3$: the amount four is missing), and why $2 \cdot 3 = 6$ is ($3 \le 1 + 3$). It also connects to the weird numbers of the previous essay: a weird number is abundant with a gap in its reachable amounts at the excess, and a practical number is one with no gaps at all. The census found the two methods — rule and direct search — agreeing on all 3,000 numbers, which is as much a check on the search as on the rule.

Why the rule is right #

The Stewart–Sierpiński rule deserves its proof, because the proof is the clearest account of what practicality is. Suppose $m$ is practical, so its divisors make every amount up to their sum $\sigma(m)$, and let $p$ be a prime not dividing $m$ with $p \le \sigma(m) + 1$. The claim is that $mp$ is practical too.

The divisors of $mp$ are the divisors of $m$, together with $p$ times each of them. To make an amount $t$ up to $\sigma(mp) = \sigma(m)(p + 1)$, divide $t$ by $p$: write $t = pq + r$ with $0 \le r < p$. If $q$ is at most $\sigma(m)$, make $q$ from divisors of $m$ and multiply them all by $p$, which gives $pq$ from the second kind of divisor; then make the remainder $r$, which is less than $p \le \sigma(m) + 1$ and so at most $\sigma(m)$, from the first kind. The two selections use different divisors, so nothing is used twice. If $q$ is larger than $\sigma(m)$, the amount is close to the total, and the same argument applied to $\sigma(mp) - t$, choosing what to leave out, does it. For a prime power $p^k$ the same step is repeated $k$ times.

Conversely, if some prime $p$ in the factorisation is larger than one more than the divisor sum $\sigma(m)$ of the part before it, then the amount $\sigma(m) + 1$ cannot be made: every divisor at least as large as $p$ is too big, and every smaller one divides $m$, so together they reach only $\sigma(m)$. The rule is the condition that no such gap ever opens, checked one prime at a time.

That is the same reasoning as a set of weights for a balance with one pan. Weights $1, 2, 4, 8$ weigh every load up to fifteen, and a new weight $w$ extends the range without a gap exactly when $w$ is at most one more than the current range. Practical numbers are the numbers whose divisors are such a set of weights, and the rule says the primes must arrive slowly enough for the weights to keep up — which is also why powers of two, the weights that cover every amount with nothing to spare, are practical.

Counted like the primes #

How many practical numbers are there below a large $x$? The figure below counts them up to ten million.

The surprise is the comparison. The primes up to $x$ number about $x/\log x$, by the prime number theorem. The practical numbers, which are defined by a property that sounds like the opposite of primality — a prime has as few divisors as possible, a practical number has divisors dense enough to make every amount — number about $1.336\,x/\log x$. Both thin out at the same rate, the rate of $1/\log x$, and the practical numbers are about a third more common than the primes at every scale the figure reaches. At ten million the practical count times $\log x / x$ is $1.3364$.

That the practical numbers have this density was a long road. Georges Tenenbaum came close in the 1980s, Eric Saias proved in 1997 that their count lies between constant multiples of $x/\log x$, and Andreas Weingartner proved in 2015 that the ratio tends to a definite constant, which he later computed to be $1.33607\ldots$. The census’s $1.3364$ at ten million is already within a few ten-thousandths of the limit.

Why $\log x$? Heuristically, a number is practical when its primes, taken in order, never jump too far ahead of the divisor sum built so far — when each prime is at most about the size of the product of the earlier prime powers. That is a condition on how fast the sequence of a number’s prime factors grows, and numbers whose prime factors grow slowly enough turn out to have density proportional to $1/\log x$ for the same kind of reason that primes do: both conditions amount to the number having no large gap in a multiplicative sequence attached to it.

Goldbach, proved, for practical numbers #

The resemblance to the primes goes further, and it ends in theorems that for primes are among the most famous open problems.

Goldbach’s conjecture says every even number above two is a sum of two primes; it is open, though verified far beyond any range a figure can show. Its practical-number counterpart is a theorem: Giuseppe Melfi proved in 1996 that every even number is a sum of two practical numbers. The figure counts the representations for every even number up to 4,000 and finds none with no representation, and the counts spread out in a widening band just as the Goldbach comet does for primes.

Melfi proved in the same paper that there are infinitely many triples $n - 2$, $n$, $n + 2$ of practical numbers — eleven of them below 4,000 — the practical counterpart of the twin prime conjecture, also open for primes. The proofs work because practical numbers can be built: multiplying a practical number by a suitable factor keeps it practical, so practical numbers with prescribed properties can be constructed, while primes cannot be manufactured at all. The density is the same; the structure is different; and the structure is what makes the theorems provable. For the primes, the obstacle is specific and well understood: sieve methods, which are the natural tools for Goldbach-type problems, cannot distinguish numbers with an even number of prime factors from those with an odd number, and so cannot certify that a number they produce is prime rather than a product of two primes. Practical numbers carry no such parity condition — a practical number may have any number of prime factors — and the obstacle simply does not arise.

The surprising connection #

Primes and practical numbers sit at opposite ends of the divisor spectrum. A prime has only the divisors $1$ and itself, the sparsest set there can be, and a practical number has divisors dense enough to make every amount. Yet both are counted by $x/\log x$, up to a constant, and both satisfy Goldbach-type statements — conjecturally for primes, provably for practical numbers. Margenstern, who catalogued the analogies in 1991, conjectured further practical analogues of prime theorems, and several have since been proved.

What makes this more than a coincidence of two counts is the reason given above. Both properties are conditions on the multiplicative structure of a number that a “random” number satisfies with probability about $1/\log$ of its size. For the primes, the condition is having no small factor; for practical numbers, having small factors that never fall too far behind one another. The prime number theorem and Weingartner’s theorem are two instances of a single principle about multiplicative conditions — that conditions on how a number’s prime factors are spaced cost a logarithm — and the practical numbers are the instance where enough structure survives to prove what for the primes can only be conjectured.

A constant the counts approach too slowly to show #

The density figure stops at ten million. The ratio $1.3364$ at the top of the figure is close to Weingartner’s constant, but the figure cannot show the convergence: the ratio wanders by a hundredth over the range, and the theorem’s error term shrinks only like $\log\log x / \log x$. That the limit is $1.33607\ldots$ is Weingartner’s computation, reported, not the figure’s.

The Goldbach counts are a range, and the theorem is all even numbers. Every even number up to 4,000 has a representation, and the counts are far from zero for most. That every even number has one is Melfi’s theorem; the figure is its picture on a range, and, as with the primes, a picture on a range would be consistent with a theorem or a conjecture alike.

The rule-against-search check is for three thousand numbers. The Stewart–Sierpiński rule is a theorem with a short proof, and the figure’s agreement on 3,000 numbers checks the search implementation as much as the rule.

Still open: the analogies that remain conjectures #

Several practical-number analogues of prime conjectures are still open. Margenstern’s list of 1991 included statements about sums of practical numbers and primes, and about practical numbers in polynomial sequences, modelled on the open problems about primes; some have since been proved, by constructions of the kind Melfi used, and others have resisted. The general principle that practical numbers obey every prime-like statement their constructibility permits has not been made precise — which statements about primes have practical analogues that are provable, and why exactly those, is not known.

And the oldest question in the family sits underneath them all. Every even perfect number is practical, as shown above. Whether any odd perfect number exists is unknown; an odd number is never practical, so the property cannot help. Divisors that make every amount, divisors that make exactly the number, and divisors that make everything except the number — practical, perfect and weird — are three answers to one question about what a number’s parts can add up to, and each has its own open problem at the place where oddness enters.