Abundant, and still not a sum of its parts

A perfect number is the sum of its proper divisors: $6 = 1 + 2 + 3$, $28 = 1 + 2 + 4 + 7 + 14$. An abundant number has divisors adding to more than itself — twelve’s add to sixteen — and about a quarter of all numbers are abundant. A deficient one has divisors adding to less.

For an abundant number there is a natural follow-up question. Its divisors overshoot it in total, so perhaps some of them add to it exactly. Twelve passes: $12 = 2 + 4 + 6$, and also $1 + 2 + 3 + 6$. Eighteen passes: $18 = 3 + 6 + 9$. Twenty passes: $20 = 1 + 4 + 5 + 10$. A number that is the sum of some of its proper divisors is called semiperfect, and for a while it looks as if every abundant number is one.

Seventy is not. Its proper divisors are $1, 2, 5, 7, 10, 14$ and $35$, and they add to $74$, so seventy is abundant. But no selection of them, each used at most once, adds to $70$. Stanley Benkoski named such numbers weird in 1972: abundant, and yet not a sum of any of their parts.

Why seventy fails: the excess #

The figure shows which totals the divisors of seventy can make, and the two gaps in the strip are the whole explanation. A selection of divisors adds to $70$ exactly when the divisors left out add to $74 - 70 = 4$, the excess. So seventy is a sum of its divisors exactly when its excess is. And four cannot be made from seventy’s small divisors: the only ones below four are $1$ and $2$, and $1 + 2 = 3$. Every other total up to $74$ can be made — the strip has only those two gaps, $4$ and $70$, mirror images of each other through the middle — and the one that matters is missing.

That turns a search through $2^7 = 128$ selections into a glance at the smallest divisors. A number fails to be semiperfect when its excess is small and its small divisors are sparse. Seventy is $2 \cdot 5 \cdot 7$: it has the divisor $1$ and the divisor $2$, and then jumps to $5$, leaving a gap at $4$ that nothing fills. Twelve, by contrast, is $2^2 \cdot 3$, with divisors $1, 2, 3, 4$ crowded at the bottom, and its excess of $4$ is a divisor outright.

The same reasoning explains why semiperfect numbers are so common. A number whose small divisors include $1, 2, 3, 4, 6$ — any multiple of twelve — can make every total up to sixteen from them, so any excess up to sixteen is covered. Most abundant numbers are multiples of small abundant numbers, and those inherit enough small divisors to cover their excess. Weird numbers are the abundant numbers that manage to overshoot without having many small divisors, which is a delicate balance.

Every weird number below twenty thousand #

The census below checks every abundant number up to twenty thousand by computing every total its divisors can make up to its excess.

There are thirty-six weird numbers below twenty thousand, against 4,953 abundant numbers: about one abundant number in a hundred and forty. The first ten are $70$, $836$, $4030$, $5830$, $7192$, $7912$, $9272$, $10430$, $10570$ and $10792$, matching the published list. After seventy the next is more than ten times larger, and the gaps are irregular.

Two structural facts organise the list. First, a multiple of a semiperfect number is semiperfect: if $n$ is a sum of some of its divisors, then $kn$ is the sum of $k$ times those divisors, which are divisors of $kn$. So a weird number cannot be a multiple of any semiperfect number, and every abundant number that divides a weird number must itself be weird. Second, multiples of weird numbers can be weird again, but need not be — $140 = 2 \cdot 70$ is semiperfect, since its divisors add to $196$ and the excess $56$ is $35 + 14 + 7$, all divisors. The nine larger dots are the primitive weird numbers in the range, those not divisible by a smaller weird number. Giuseppe Melfi proved in 2015 that there are infinitely many primitive weird numbers, settling a question Paul Erdős had asked.

The weird numbers are rare but not vanishingly so. Benkoski and Erdős proved in 1974 that they have a positive density: a definite small proportion of all numbers is weird, as a positive proportion is abundant. The census’s thirty-six below twenty thousand is a proportion of about one in five hundred and fifty, and the proportion is believed to settle near that.

Only a little abundant #

Since a number is weird exactly when its excess cannot be made from its divisors, a large excess should make weirdness hard. The figure tests that.

Every weird number in the range has an excess below 7.1 per cent of itself, while abundant numbers in general overshoot by up to fifty per cent and more. The prediction is borne out completely: a large excess can almost always be made from small divisors, and only a number that is barely abundant can miss. Seventy overshoots by four, under six per cent; $836 = 2^2 \cdot 11 \cdot 19$ overshoots by $8$, under one per cent. Among the 1,035 abundant numbers in range that overshoot by less than a tenth, one in twenty-nine is weird; above a tenth, none is.

The pattern also says where to look for weird numbers: just over the line between deficient and abundant. Numbers of the form $2^k \cdot p \cdot q$, with two primes chosen so that the divisor sum barely exceeds twice the number, are the standard source of weird numbers, and most of the primitive ones in the census have that shape: $70 = 2 \cdot 5 \cdot 7$, $836 = 4 \cdot 11 \cdot 19$, $5830 = 2 \cdot 5 \cdot 11 \cdot 53$. Their small divisors are powers of two and little else, and powers of two can make every total up to their sum but no more — so the excess has to land just beyond what the powers of two reach.

The excess, just out of reach #

The table below takes the primitive weird numbers of the census and lays out the mechanism row by row.

The pattern is almost too clean. In nearly every row the divisors small enough to help are powers of two — $1, 2$; or $1, 2, 4$; or $1, 2, 4, 8$ — and powers of two make every total up to their sum and nothing beyond, which is the reason every number has a binary expansion. With $1, 2, 4, 8$ every total from one to fifteen is reachable. And the excess in those rows is exactly sixteen, the first total out of reach. Seventy’s excess is four, one more than $1 + 2$; 836’s is eight, one more than $1 + 2 + 4$; 7,192’s is sixteen.

That is what a weird number of the commonest kind is: a number of the form $2^k p q$ whose divisors overshoot it by exactly $2^{k+1}$, so that the powers of two among its divisors fall one short of covering the excess and no other divisor is small enough to help. The one row that breaks the pattern, 9,272, has an excess of fifty-six and small divisors that include $19$ and $38$; even so they cannot make fifty-six, because the powers of two make only up to fifteen and $19 + 38 = 57$ overshoots by one. Weirdness is the arithmetic of near misses.

Seen this way the primes $p$ and $q$ in $2^k p q$ have a precise job: to make the divisor sum overshoot $2n$ by exactly $2^{k+1}$. That is a single equation in two primes, $\sigma(2^k p q) = 2 \cdot 2^k p q + 2^{k+1}$, and it can be solved exactly. Write $M = 2^{k+1} - 1$, the sum of the powers of two dividing $2^k$. The divisor sum of $2^k pq$ is $M(p + 1)(q + 1)$, and setting it equal to $2^{k+1}pq + 2^{k+1}$ and rearranging gives

$$(p - M)(q - M) = M^2 - 1.$$

For $k = 3$, $M = 15$ and the right side is $224$, and its factorisations $14 \cdot 16$, $8 \cdot 28$, $4 \cdot 56$ and $2 \cdot 112$ give the prime pairs $(29, 31)$, $(23, 43)$, $(19, 71)$ and $(17, 127)$ — exactly the four rows of the table with excess sixteen. For each $k$ there are only finitely many such pairs, one for each way of factoring $M^2 - 1$ into two numbers that both become primes when $M$ is added; infinitely many weird numbers of this shape would need infinitely many $k$ with at least one such factorisation. Melfi’s proof that primitive weird numbers are infinite works along these lines, with a theorem about primes in place of luck.

Sums of distinct parts #

Choosing divisors that each appear at most once is choosing a partition into distinct parts, the kind of partition Euler counted with a product of factors $(1 + x^d)$, one for each available part. The totals a number’s divisors can make are the exponents that appear in $\prod_{d} (1 + x^d)$, the product taken over its proper divisors. Seventy’s product has every exponent from $0$ to $74$ except $4$ and $70$; a number is semiperfect when its own exponent appears; and the census is the multiplication of those polynomials, done with the coefficients replaced by yes or no.

The same viewpoint explains the mirror symmetry of the hero strip. Replacing every chosen set of divisors by the set left out sends a total $t$ to $74 - t$, so the reachable totals are symmetric about the middle, $37$, and the gaps come in pairs: $4$ and $70$. Every weird number’s strip has that symmetry, with its gaps at the excess and at the number itself, and for the same reason. It is the aliquot sum’s cousin: where the aliquot sum adds all the proper divisors and asks what comes out, the weird-number question asks which amounts can be made from some of them, and which cannot.

The odd question #

Every weird number in the census is even. That is not a fact about the census’s range: nobody has ever found an odd weird number.

Odd abundant numbers are themselves rare. The smallest is $945$, whose divisors add to $975$, and there are only 210 below a hundred thousand, compared with about 24,800 abundant numbers in all. Every one of the 210 is semiperfect: its excess can be made from its divisors. Searches by computer have pushed the bound far beyond the census: no odd weird number exists below $10^{21}$.

The reason odd weird numbers are hard to find is the reason odd abundant numbers are hard to find. An odd number’s divisors cannot include two, so its smallest divisors are spread out — $1, 3, 5, 7, 9, \ldots$ — and to be abundant at all it needs many small odd prime factors, $945$ has three distinct ones. Many small factors mean many small divisors, which mean that the excess can almost always be made. The sparse small divisors that weirdness requires and the dense small divisors that odd abundance requires pull in opposite directions, and whether they can ever be reconciled is not known.

The surprising connection: the oldest open question, asked of a weaker property #

That makes the odd weird number a younger sibling of the most famous open question about divisors: whether an odd perfect number exists. A perfect number is one whose whole set of proper divisors adds to it. A semiperfect number is one for which some set does. A weird number is an abundant number for which no set does. The odd perfect number problem asks whether an odd number can be a sum of all its parts; the odd weird number problem asks whether an odd abundant number can fail to be a sum of any of them.

Both are about the same tension: odd numbers have no factor of two, and their divisors are therefore too sparse to sum neatly. For perfect numbers the tension shows as a wall of conditions — an odd perfect number must exceed $10^{1500}$ and have at least ten distinct prime factors. For weird numbers it shows as the opposite: an odd abundant number has so many small factors that its excess is always covered. In both cases the computations say “none so far”, the heuristics say “probably none”, and the proofs say nothing.

A subset-sum problem in disguise #

Deciding whether a number is weird is an instance of the subset-sum problem: given a list of whole numbers and a target, is there a selection adding to the target? In general that problem is hard — it is one of the standard problems for which no fast method is known, and for which a fast method would give fast methods for a great many others. The census solves it the way such problems are solved when the numbers are small: by marking every total that can be reached, one divisor at a time, which takes time proportional to the number of divisors times the excess.

For divisors the problem is easy in practice for the reason the excess figure shows: weird numbers have small excesses, and small targets are cheap. The difficulty of subset-sum is in large targets with no structure, and divisors have so much structure — they are closed under taking divisors, and the small ones are powers of a few primes — that a number’s divisors almost never pose a hard instance. That the question of odd weird numbers is open is not because each case is hard to check. It is because there are infinitely many cases and no argument that covers them.

Complete below twenty thousand, silent above it #

Every statement about the range is complete, and nothing beyond it follows. The thirty-six weird numbers below twenty thousand and the 210 odd abundant numbers below a hundred thousand are all there are, checked by computing every reachable total. That the weird numbers have positive density, that infinitely many are primitive, and that no odd one lies below $10^{21}$ are theorems and computations reported from the literature, not made here.

The excess bound is an observation. Every weird number in the census overshoots by under 7.1 per cent. There is no theorem in this essay saying a weird number must overshoot by little, and in principle a weird number with a larger excess and unusually sparse small divisors is not ruled out; the figure says only that none occurs in range.

The structural shape $2^k p q$ describes most, not all. Several weird numbers in the census have three or more odd prime factors, and the primitive ones of the shape $2^k p q$ are a description of the commonest kind rather than a classification.

Still open: an odd one #

Whether an odd weird number exists is open. Erdős offered a prize for its resolution, and it has stayed open through every increase in computing power. A proof that none exists would need to show that every odd abundant number has enough small divisors to make its excess — an argument about the fine structure of divisors of odd numbers that nobody has found. A counterexample would need an odd number with very few small divisors that is nonetheless abundant, a combination the heuristics say is extremely rare but not impossible.

There is also a question about weirdness’s own fine structure, and about how it sits beside the other divisor properties — perfection, abundancy, the ratio of the divisor sum to the number. The primitive weird numbers are infinite, by Melfi’s theorem, and most known ones have the form $2^k p q$, but whether there are infinitely many primitive weird numbers with any given number of odd prime factors, and how they are distributed, is known only in part. The divisors of a number decide whether it is perfect, abundant, semiperfect or weird, and what those divisors add to keeps producing questions that are easy to state, easy to test, and hard to settle.