Integer complexity

In number theory, the integer 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 proportional to 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 eight.

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, ... (sequence A005245 in the OEIS)

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

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (sequence A005520 in the OEIS)

Upper and lower bounds

The question of expressing integers in this way was originally considered by Mahler & Popken (1953). They asked for the largest number with a given complexity $k$ ;^[1] later, Selfridge showed that this number is

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

For example, when $k = 10$ , $x = 2$ and the largest integer that can be expressed using ten ones is $2232 = 36$ . Its expression is

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

Thus, the complexity of an integer $n$ is always at least $3 log 3 n$ , and it is also always at most proportional to the logarithm. More precisely, the complexity of any integer $n$ is at most $3 log 2 n$ (approximately $4.755 log 3 n$ ): an expression of this length for $n$ can be found by applying Horner's method to the binary representation of $n$ .^[2] Almost all integers have a representation whose length is bounded by a logarithm with a smaller constant factor, $3.529 log 3 n$ .^[3]

Computational complexity

The complexities of all integers up to some threshold $N$ can be calculated in total time $O (N 1.230175)$ .^[4]

References

^ Mahler, K.; Popken, J. (1953), "On a maximum problem in arithmetic", Nieuw Archief voor Wiskunde, 1: 1–15, MR 0053986.
^ Guy, Richard K. (1986), "Some suspiciously simple sequences", Unsolved Problems, American Mathematical Monthly, 93 (3): 186–190, doi:10.2307/2323338, MR 1540817.
^ Shriver, Christopher E. (2015), Applications of Markov chain analysis to integer complexity, arXiv:1511.07842.
^ Arias de Reyna, J.; van de Lune, J. (2014), Algorithms for determining integer complexity, arXiv:1404.2183

External links

Weisstein, Eric W. "Integer Complexity". MathWorld.

[1] Mahler, K.; Popken, J. (1953), "On a maximum problem in arithmetic", Nieuw Archief voor Wiskunde, 1: 1–15, MR 0053986.

[2] Guy, Richard K. (1986), "Some suspiciously simple sequences", Unsolved Problems, American Mathematical Monthly, 93 (3): 186–190, doi:10.2307/2323338, MR 1540817.

[3] Shriver, Christopher E. (2015), Applications of Markov chain analysis to integer complexity, arXiv:1511.07842.

[4] Arias de Reyna, J.; van de Lune, J. (2014), Algorithms for determining integer complexity, arXiv:1404.2183

[1]

[2]

[3]

[4]