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 within a constant factor of the logarithm of the given integer.

Also, there exist one more definition of complexity. Complexity of an integer n is the minimum number of steps required to get n, where at each step one can either calculate a sum or a product of any two previously obtained numbers. The first number in the set to be one. Upper bound to complexity by new definition is 3*ln(n)\ln(ln(n)).

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)

By new approach, the number 11 be represented using for steps:

[1] 1+1 = 2

[2] 1+2 = 3

[3] 3*3 = 9

[4] 2+9 = 11

For proof that one can not get 11 less then 4 steps we check all numbers with complexity less then 4:

Complexity 0: 1

Complexity 1: 2

Complexity 2: 3, 4

Complexity 3: 5, 6, 8, 9, 16

The upper bound for complexity you can see in this link: http://nbashaev.pythonanywhere.com/integer_complexity/

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

2, 3, 5, 7, 13, 23, 59, 211, 619.

Also, Mordosevich's hypothesis try to describes all of smallest numbers.

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 at least $3 log 3 n$ . The complexity of $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]

By new approach, now gived asymptotically optimal monotonous upper and lower bounds but we do not know something about not-monotonous bounds.

The largest number with complexity n $\in$ $\mathbb{N}$ is $2^{2^{n}}$ (the largest number with complexity 0 is 1). For proof you can use induction, also, Andrey Mordosevich proof this.

About the lower bound, it is f = k*($\frac{ln(n)}{ln(ln(n))}$, $\frac{1}{2}$ < k < 3. Also, Andrey Mordosevich proof this.

Mordosevich's hyphotesis: All a is prime numbers, g>0. Where a = smallest number with complexity g.

Algorithms and counterexamples

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

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 $n$ is obtained either by subtracting one from $n$ or by expressing $n$ 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 $p$ is one plus the complexity of $p - 1$ .^[5]

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, Bibcode:2015arXiv151107842S.
^ Cordwell, K.; Epstein, A.; Hemmady, A.; Miller, S.; Palsson, E.; Sharma, A.; Steinerberger, S.; Vu, Y. (2017), On algorithms to calculate integer complexity, arXiv:1706.08424, Bibcode:2017arXiv170608424C
^ Fuller, Martin N. (February 1, 2008), Program to calculate A005245, A005520, A005421, OEIS, retrieved 2015-12-13.

External links

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

[guy-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, Bibcode:2015arXiv151107842S.

[4] Cordwell, K.; Epstein, A.; Hemmady, A.; Miller, S.; Palsson, E.; Sharma, A.; Steinerberger, S.; Vu, Y. (2017), On algorithms to calculate integer complexity, arXiv:1706.08424, Bibcode:2017arXiv170608424C

[5] Fuller, Martin N. (February 1, 2008), Program to calculate A005245, A005520, A005421, OEIS, retrieved 2015-12-13.

[1]

[2]

[3]

[4]

[5]