The fewest ones that build a number
Worth reading first: One way to factor, and no other · Most numbers are missing from the table.
How many ones does it take to write a number, if the only operations allowed are addition and multiplication, with brackets as needed? The number 6 can be written as , using six ones, but uses only five, and nothing uses fewer. The number 7 needs six: . This count is called the complexity of the number, written , and it was studied by Kurt Mahler and Jan Popken in 1953 and popularised by Richard Guy, who asked in 1986 whether its behaviour could be predicted.
The question sounds like a puzzle and turns out to be a probe of how addition and multiplication interact. One way to factor began this collection’s account of the primes with the statement that every number is a product of primes in one way only — a statement about multiplication alone. Complexity mixes the two operations, and asks how cheaply a number can be reached by a route that alternates between them. A number with a cheap factorisation is cheap; a prime has no factorisation to use, and its cheapest expression must end with an addition. How much more that costs is the subject of this essay, and every number up to 30,000 has been measured.
Every number between two bounds
The computation is a table. A cheapest expression for is either a sum or a product of two smaller numbers, each built as cheaply as possible, so
with . Filling in the table from 1 upwards — dynamic programming — gives every number’s complexity in a few tenths of a second up to 30,000. The hero plots the first 2,000 against , and they form a band with sharp edges.
The bottom edge is the line . Mahler and Popken proved that no number does better: the most that ones can build is , by grouping them in threes and multiplying, and so . Equality holds only when is a power of 3, which the figure’s checks confirm for , each costing exactly three ones per factor of three. The reason threes are best is a small optimisation: splitting ones into equal groups of size and multiplying builds , and is largest among whole numbers at , since beats and . Grouping in threes squeezes the most out of each one.
The top edge comes from building a number from its binary digits by Horner’s rule: start from 1, and for each further binary digit double and add the digit, or . Doubling costs two ones and adding one costs one, so a number with binary digits costs at most , and every number satisfies . The figure draws that bound dashed; most numbers sit well below it, close to the lower line, because base-three thinking is usually available.
Binary beats ternary in the worst case
The two bounds suggest a puzzle. Threes are the most efficient building block, so why is the upper bound built from binary digits rather than ternary ones? Try the ternary version of Horner’s rule: start from the leading digit, and for each further base-three digit multiply by 3 and add the digit, 0, 1 or 2. Multiplying by 3 costs three ones and adding the digit costs up to two, so a ternary digit costs up to five ones, and a number with ternary digits costs up to about , which is . The binary rule costs up to three ones per binary digit, , which is . In the worst case, binary wins. It is not far from optimal even where optimal is hardest: 1439, written 10110011111 in binary, costs 28 ones by the binary rule — one for the leading digit, two for each of ten doublings and one for each of the seven further ones — against the true minimum of 26.
On average the two are closer. A random binary digit is 1 half the time, so the binary rule costs on average 2.5 ones per binary digit, about ; a random ternary digit adds 0, 1 or 2 with equal chances, an average of one, so the ternary rule costs about 4 ones per ternary digit, . Neither rule is close to the truth, which hugs much more tightly, because the cheapest expressions do not commit to one base. They factor whatever factors well and add small corrections only where needed — and the corrections are always small, ones and twos, as the expressions in the next figure show.
That is the real content of the hero’s band. A fixed base gives an upper bound with a fixed constant, and the true costs sit far below every such bound because an optimal expression chooses a different “base” at every step, whichever factor of the current number, or of a number one or two away, happens to be cheap. The complexity of is a measure of how well the numbers near , and near its factors, and near their factors, can be broken into small pieces.
Shortest expressions, read back
The table records not only each number’s cost but how it was achieved, so shortest expressions can be read back. The figure lists some, writing numbers up to 5 as numerals: each such numeral costs its own value in ones, since , , or , and are all as cheap as possible. Each expression is re-evaluated as a check on both its value and its count.
The pattern is visible at once. Cheap numbers are products of small factors: at five ones, at twelve. Expensive numbers are one or two more than a cheap multiple, because the only way to reach a prime, or a number with awkward factors, is to add to something nearby that factors well. And the additions nest: , where and . Every layer of the expression is a near-miss multiplication repaired by adding one or two, and 1439 needs three layers of repair to reach. It costs 26 ones, the most of any number in the range relative to its size.
That nesting is the structure behind complexity’s difficulty. To know , one needs and , which need the factorisations of and , which in turn need the complexities of their factors, each of which may need its own predecessors. Complexity braids together the additive structure — being next to something — and the multiplicative structure — factoring well — in a way that neither alone describes. Sums with too few primes met the same braid from another direction, in the abc conjecture’s claim that a sum of two numbers built from few primes cannot itself be built from few primes too often.
The smallest numbers that need each count
Turning the table around, for each ask for the smallest number that needs ones. The sequence runs 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467, 683, 719, 1223, 1438, 1439, 2879, … and the figure plots it on a logarithmic scale against , the largest number that ones can build.
The two curves run nearly parallel. The smallest number needing ones is always a roughly constant factor below the largest number ones can make, which means the costs are crowded: there is no large range of numbers that need many more ones than their size suggests. The most expensive number in the range, measured by the ratio , is 1439, at . Below 30,000 nothing else reaches that ratio, and computations reported in the literature have found nothing higher far beyond.
There is a curious near-coincidence at the top: 1438 is the smallest number needing 25 ones and 1439 the smallest needing 26. Expensive numbers come in such clusters because an expensive number makes and candidates for the next record — doubling and adding one is the cheapest way to extend an expression — and 2879, which needs 27, is .
A prime costs one more than its predecessor
A prime has no factorisation, so its cheapest expression is a sum, . The simplest sum is , costing , and one might expect cleverer splits to beat it sometimes — with both and cheap. The figure checks every prime from 3 to 30,000, and in all 3,244 cases the cheapest expression costs exactly . No prime in the range has a cheaper split. Composites behave quite differently: going from to a composite , the cost rises by 1 only 29% of the time, stays the same 41% of the time, and falls by as much as 5, since a composite with good factors can be far cheaper than its predecessor.
The pattern for primes was conjectured to hold forever, and it is false — but only far beyond any table. Janis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis and Kārlis Podnieks searched to in 2012 and found the first prime that breaks it, 353,942,783, whose cheapest expression is a sum of two numbers with cheap structure rather than its predecessor plus one. A pattern that holds for every prime up to a third of a billion is still not a theorem. This is the essay’s warning in miniature: in complexity, as in much of number theory, the small cases mislead, and the data of the figure cannot distinguish a law from a long coincidence.
Neighbours that share nothing
The prime pattern has a structural reason behind it, even though it eventually fails. A number and its predecessor share no prime factor — any prime dividing both would divide their difference, 1 — so and are built from entirely different primes. Two neighbours share out their small primes measured how the small primes divide themselves between consecutive numbers, and found that one of the pair tends to be the smooth one, rich in small factors, and the other rough. For complexity, the smooth neighbour is the cheap one. A prime is as rough as a number can be, so its cheapest route is almost always through a smooth neighbour, and the nearest neighbour is the one below.
For a prime to break the pattern, it needs a split in which and are both very cheap — both built mostly from twos and threes — and together cheaper than . Such splits exist only when is unusually expensive for its size, and the largest prime in a typical number found that a number’s largest prime factor is typically a sizeable power of the number, so that is usually rough in part. The counterexample at 353,942,783 is a prime for which such a split exists; why it is the first, and how often such primes occur beyond it, is not something the search explains.
The composites show the other side. When is prime and is a product of small primes, the cost falls sharply from one to the next; the largest drop in the range, five ones, happens six times, and every time at a smooth number sitting just above an expensive prime: 1440 just above 1439, where the cost falls from 26 to 21; 8,748, which is , just above the prime 8,747; and 21,600 just above 21,599, the smallest number needing 34 ones. The figure’s spread of differences for composites, from to , is the spread of how much better factors than , and the primes’ single bar at says that, in the range measured, nothing beats approaching a prime from the number just below it. A factorisation that hides its primes showed what happens to factorisation when the numbers allowed are restricted; complexity is the opposite experiment, restricting nothing and asking only how cheaply the two operations, together, can reach each number.
Powers of two and three
The products of twos and threes are the numbers that the lower bound’s argument likes best, and the figure measures every one up to 30,000. Each costs exactly , the cost of writing out its factors and multiplying: no cleverer route through additions ever helps. For powers of three this is Mahler and Popken’s theorem. For powers of two it is the conjecture that , which has been verified far beyond this table but is not proved. Nobody can rule out that some enormous power of two has an expression cheaper than — that adding and multiplying cleverly could beat simple doubling.
The difficulty is that the lower bound is not tight for powers of two. It gives , which is less than , and closing the gap between and requires showing that no expression for can use the more efficient threes. Partial results — Harry Altman and Joshua Zelinsky proved for every up to 21, and later work extended the range — rest on careful classification of the numbers whose complexity is close to the lower bound, and each extension of the range has needed more of it.
What the table cannot show
The figures report exact values, but only up to 30,000, and the patterns they show are the patterns of small numbers. The prime pattern fails at 353,942,783; the powers-of-two pattern might fail somewhere, or might be provable; the record ratio at 1439 might be exceeded, though the searches say not. A table this size cannot speak to any of these. What it does show is the band: every number between the two bounds, and the shape of the cheapest expressions. Those are theorems, and the table illustrates them; the rest is evidence.
The table also cannot show what most numbers are missing from the table measured for products alone — how many numbers are reachable at each cost. Complexity is a minimum over expressions, and the count of numbers with a given complexity, or the average complexity of numbers up to , are quantities the figures do not draw. Whether has a limiting average value as grows, and what it would be, is not known. And the dynamic programme hides the cost of computing a single number’s complexity without computing all the smaller ones: no method is known that is fundamentally faster than building most of the table, which is part of why the prime counterexample took a search to to find.
Still open: the powers of two
Is for every ? It is the simplest open question about integer complexity, and it asks whether doubling can ever be beaten. Every computation says no. A proof would need to show that every expression for a power of two that uses an addition is wasteful, and additions are exactly what complexity’s difficulty is made of: the shape of a number’s divisors drew multiplication as a lattice where everything is visible, while an addition can join numbers whose factorisations have nothing in common. How many primes a typical number has found that typical numbers have about prime factors, so typical numbers factor badly, and their cheapest expressions are full of additions; a power of two is the opposite extreme, factoring as well as any number can, and whether that perfect factorisation is always the cheapest way to build it is still unknown.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- A sort that never looks at the answers — both name exhaustive search, lower bound, recursion
- Euclid's proof run as a machine — both name exhaustive search, prime factorisation, primes
- Running a computation backwards with little memory — both name dynamic programming, lower bound, recursion
- The order of the questions — both name dynamic programming, exhaustive search, lower bound
- A constant that holds the primes — both name exhaustive search, primes
- A line that fires all at once — both name lower bound, recursion
Named objects
A dashed tag is an object no other essay names yet.
Dynamic programmingExhaustive searchLower boundPrime factorisationPrimesRecursion