Integer complexity

Template:Short description Template:CS1 config In number theory, the complexity of an integer is the smallest number of ones that can be used to represent it using ones and any number of additions, multiplications, and parentheses. It is always within a constant factor of the logarithm of the given integer.

Example

For instance, the number 11 may be represented using eight ones:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

However, it has no representation using seven or fewer ones. Therefore, its complexity is 8.

The complexities of the numbers 1, 2, 3, ... are

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... Template:OEIS

The smallest numbers with complexity 1, 2, 3, ... are

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... Template:OEIS

Upper and lower bounds

The question of expressing integers in this way was originally considered by Template:Harvtxt. They asked for the largest number with a given complexity Template:Mvar; later, Selfridge showed that this number is

$2^x{3}^{(k-2x)/3}\text{ where }x=-kmod3.$

For example, when Template:Math, Template:Math and the largest integer that can be expressed using ten ones is Template:Math. Its expression is

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

Thus, the complexity of an integer Template:Mvar is at least Template:Math. The complexity of Template:Mvar is at most Template:Math (approximately Template:Math): an expression of this length for Template:Mvar can be found by applying Horner's method to the binary representation of Template:Mvar. Almost all integers have a representation whose length is bounded by a logarithm with a smaller constant factor, Template:Math.

Algorithms and counterexamples

The complexity $\Vert n\Vert$ of every integer Template:Mvar up to some threshold Template:Mvar can be calculated in total time $O(N{\log }^{O(1)}N)$. The complexity of a single integer $n$ can be computed in sublinear time, $O(n^{0.6514})$.

Algorithms for computing the integer complexity have been used to disprove several conjectures about the complexity. In particular, it is not necessarily the case that the optimal expression for a number Template:Mvar is obtained either by subtracting one from Template:Mvar or by expressing Template:Mvar as the product of two smaller factors. The smallest example of a number whose optimal expression is not of this form is 353942783. It is a prime number, and therefore also disproves a conjecture of Richard K. Guy that the complexity of every prime number Template:Mvar is one plus the complexity of Template:Math. In fact, $$\Vert 353942783\Vert =\Vert 353942782\Vert =63.$$ Moreover, Venecia Wang gave examples of other numbers whose integer complexity does not reflect the obvious formula for these numbers: $$\begin{array}{cc}\Vert 743\times 2\Vert =\Vert 743\Vert & =22\\ \Vert 166571\times 3\Vert =\Vert 166571\Vert & =39\\ \Vert 97103\times 5\Vert =\Vert 97103\Vert & =38\\ 2\Vert 23\Vert >\Vert 23^2\Vert & =20.\end{array}$$

External links

• Template:Mathworld