Number

The fewest ones that build a number

Build a number from ones using only addition, multiplication and brackets, and ask for the fewest ones. Six needs five, as (1+1)·(1+1+1); seven needs six. A power of three needs exactly three ones per factor, and no number does better for its size; building from binary digits never needs more than three ones per doubling. Between those bounds, the cheapest expressions are found by multiplying cheap factors and adding one. Every prime up to thirty thousand costs exactly one more than the number before it — a pattern that holds until 353,942,783.
19 min read 5 figures Decided by exhaustionSmall cases lie

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 1+1+1+1+1+11+1+1+1+1+1, using six ones, but (1+1)⋅(1+1+1)(1+1)\cdot(1+1+1) uses only five, and nothing uses fewer. The number 7 needs six: 1+(1+1)⋅(1+1+1)1 + (1+1)\cdot(1+1+1). This count is called the complexity of the number, written ∥n∥\|n\|, 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 fewest ones that build a number. 10:7 100:14 1000:21 1439:26 2000:23
Fig. 1 The fewest ones that build each number up to 2,000, against log⁡3n\log_3 n. Every number lies between 3log⁡3n3\log_3 n, touched only by the powers of 3, and 3log⁡2n3\log_2 n, the cost of building from binary digits.

The computation is a table. A cheapest expression for nn is either a sum a+ba + b or a product a⋅ba \cdot b of two smaller numbers, each built as cheaply as possible, so

∥n∥=min⁡(min⁡a+b=n∥a∥+∥b∥, min⁡a⋅b=n∥a∥+∥b∥),\|n\| = \min\Bigl(\min_{a + b = n} \|a\| + \|b\|,\ \min_{a \cdot b = n} \|a\| + \|b\|\Bigr),

with ∥1∥=1\|1\| = 1. 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 log⁡3n\log_3 n, and they form a band with sharp edges.

The bottom edge is the line 3log⁡3n3\log_3 n. Mahler and Popken proved that no number does better: the most that kk ones can build is 3k/33^{k/3}, by grouping them in threes and multiplying, and so ∥n∥≥3log⁡3n\|n\| \ge 3 \log_3 n. Equality holds only when nn is a power of 3, which the figure’s checks confirm for 3,9,27,…,19,6833, 9, 27, \ldots, 19{,}683, each costing exactly three ones per factor of three. The reason threes are best is a small optimisation: splitting kk ones into equal groups of size mm and multiplying builds mk/mm^{k/m}, and m1/mm^{1/m} is largest among whole numbers at m=3m = 3, since 31/3=1.4423^{1/3} = 1.442 beats 21/2=1.4142^{1/2} = 1.414 and 41/4=1.4144^{1/4} = 1.414. 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, 2x2x or 2x+12x + 1. Doubling costs two ones and adding one costs one, so a number with dd binary digits costs at most 3(d−1)+13(d - 1) + 1, and every number satisfies ∥n∥≤3log⁡2n\|n\| \le 3 \log_2 n. 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 tt ternary digits costs up to about 5t5t, which is 5log⁡3n5 \log_3 n. The binary rule costs up to three ones per binary digit, 3log⁡2n3 \log_2 n, which is 3log⁡23⋅log⁡3n=4.755log⁡3n3 \log_2 3 \cdot \log_3 n = 4.755 \log_3 n. 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 3.96log⁡3n3.96 \log_3 n; 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, 4log⁡3n4 \log_3 n. Neither rule is close to the truth, which hugs 3log⁡3n3 \log_3 n 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 nn is a measure of how well the numbers near nn, and near its factors, and near their factors, can be broken into small pieces.

Shortest expressions, read back

Shortest expressions in ones. 6=2·3 [5]; 7=1 + 2·3 [6]; 11=1 + 2·5 [8]; 17=1 + 2·2·4 [9]; 23=1 + 2·(1 + 2·5) [11]; 46=1 + 3·3·5 [12]; 47=1 + 1 + 3·3·5 [13]; 719=1 + 2·(1 + 1 + 3·(1 + 2·3)·(1 + 2·2·4)) [23]; 1439=1 + 2·(1 + 2·(1 + 1 + 3·(1 + 2·3)·(1 + 2·2·4))) [26]
Fig. 2 Shortest expressions recovered from the table, with small numbers written as numerals. The expensive numbers are built as one or two more than a cheap multiple.

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 2=1+12 = 1+1, 3=1+1+13 = 1+1+1, 4=(1+1)(1+1)4 = (1+1)(1+1) or 1+1+1+11+1+1+1, and 5=1+1+1+1+15 = 1+1+1+1+1 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: 6=2⋅36 = 2 \cdot 3 at five ones, 46=1+3⋅3⋅546 = 1 + 3\cdot 3\cdot 5 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: 1439=1+2⋅(1+2⋅(1+1+3⋅7⋅17))1439 = 1 + 2\cdot(1 + 2\cdot(1 + 1 + 3 \cdot 7 \cdot 17)), where 7=1+2⋅37 = 1 + 2\cdot 3 and 17=1+2⋅2⋅417 = 1 + 2\cdot 2 \cdot 4. 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 ∥n∥\|n\|, one needs ∥n−1∥\|n - 1\| and ∥n−2∥\|n - 2\|, which need the factorisations of n−1n - 1 and n−2n - 2, 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

The smallest number needing each count of ones. 2:2 3:3 4:4 5:5 6:7 7:10 8:11 9:17 10:22 11:23 12:41 13:47 14:59 15:89 16:107 17:167 18:179 19:263 20:347 21:467 22:683 23:719 24:1223 25:1438 26:1439 27:2879 28:3767 29:4283 30:6299 31:10079 32:11807 33:15287 34:21599
Fig. 3 For each count of ones, the smallest number that needs that many, against 3k/33^{k/3}, the largest that many ones can build. The two grow together, a roughly constant factor apart.

Turning the table around, for each kk ask for the smallest number that needs kk 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 3k/33^{k/3}, the largest number that kk ones can build.

The two curves run nearly parallel. The smallest number needing kk ones is always a roughly constant factor below the largest number kk 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 ∥n∥/log⁡3n\|n\| / \log_3 n, is 1439, at 26/6.619=3.92826 / 6.619 = 3.928. 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 nn makes 2n2n and 2n+12n + 1 candidates for the next record — doubling and adding one is the cheapest way to extend an expression — and 2879, which needs 27, is 2⋅1439+12 \cdot 1439 + 1.

A prime costs one more than its predecessor

A prime costs one more than the number before it. primes 1,3244; composites -5,6 -4,74 -3,435 -2,1842 -1,5652 0,10993 1,7752
Fig. 4 The change in cost from n − 1 to n, for every n up to 30,000. For primes it is always exactly +1; for composites it ranges from +1 down to −5.

A prime pp has no factorisation, so its cheapest expression is a sum, a+ba + b. The simplest sum is (p−1)+1(p - 1) + 1, costing ∥p−1∥+1\|p - 1\| + 1, and one might expect cleverer splits to beat it sometimes — p=a+bp = a + b with both aa and bb cheap. The figure checks every prime from 3 to 30,000, and in all 3,244 cases the cheapest expression costs exactly ∥p−1∥+1\|p - 1\| + 1. No prime in the range has a cheaper split. Composites behave quite differently: going from n−1n - 1 to a composite nn, 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 101210^{12} 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 nn and n−1n - 1 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 p=a+bp = a + b in which aa and bb are both very cheap — both built mostly from twos and threes — and together cheaper than p−1p - 1. Such splits exist only when p−1p - 1 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 p−1p - 1 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 n−1n - 1 is prime and nn 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 4⋅374 \cdot 3^7, 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 +1+1 to −5-5, is the spread of how much better nn factors than n−1n - 1, and the primes’ single bar at +1+1 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

Powers of two and three cost what their factors cost. 3:3 9:6 27:9 81:12 243:15 729:18 2187:21 6561:24 19683:27 2:2 6:5 18:8 54:11 162:14 486:17 1458:20 4374:23 13122:26 4:4 12:7 36:10 108:13 324:16 972:19 2916:22 8748:25 26244:28 8:6 24:9 72:12 216:15 648:18 1944:21 5832:24 17496:27 16:8 48:11 144:14 432:17 1296:20 3888:23 11664:26 32:10 96:13 288:16 864:19 2592:22 7776:25 23328:28 64:12 192:15 576:18 1728:21 5184:24 15552:27 128:14 384:17 1152:20 3456:23 10368:26 256:16 768:19 2304:22 6912:25 20736:28 512:18 1536:21 4608:24 13824:27 1024:20 3072:23 9216:26 27648:29 2048:22 6144:25 18432:28 4096:24 12288:27 8192:26 24576:29 16384:28
Fig. 5 The cost of every number 2a⋅3b2^a \cdot 3^b up to 30,000. In every cell it is exactly 2a+3b2a + 3b, the cost of multiplying the factors together.

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 2a+3b2a + 3b, 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 ∥2a∥=2a\|2^a\| = 2a, 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 (1+1)a(1+1)^a — 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 ∥2a∥≥3alog⁡32=1.893a\|2^a\| \ge 3 a \log_3 2 = 1.893 a, which is less than 2a2a, and closing the gap between 1.8931.893 and 22 requires showing that no expression for 2a2^a can use the more efficient threes. Partial results — Harry Altman and Joshua Zelinsky proved ∥2a3b∥=2a+3b\|2^a 3^b\| = 2a + 3b for every aa 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 NN, are quantities the figures do not draw. Whether ∥n∥/log⁡3n\|n\|/\log_3 n has a limiting average value as nn 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 101210^{12} to find.

Still open: the powers of two

Is ∥2a∥=2a\|2^a\| = 2a for every aa? 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 log⁡log⁡n\log\log n 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.

Named objects

A dashed tag is an object no other essay names yet.

Dynamic programmingExhaustive searchLower boundPrime factorisationPrimesRecursion