Integer complexity

Last updated June 09, 2024

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, ... (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 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]

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] In fact, one can show that $\|p\|=\|p-1\|=63$ . Moreover, Venecia Wang gave some interesting examples, i.e. $\|743\times 2\|=\|743\|=22$ , $\|166571\times 3\|=\|166571\|=39$ , $\|97103\times 5\|=\|97103\|=38$ , $\|23^{2}\|=20$ but $2\|23\|=22$ .^[6]

Related Research Articles

In number theory, Euler's conjecture is a disproved conjecture related to Fermat's Last Theorem. It was proposed by Leonhard Euler in 1769. It states that for all integers $n$ and $k$ greater than 1, if the sum of $n$ many $k$ th powers of positive integers is itself a $k$ th power, then $n$ is greater than or equal to $k$ :

In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best-known transcendental numbers are $π$ and $e$ . The quality of a number being transcendental is called transcendence.

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×10²⁰, but no general proof has been found.

10 (ten) is the even natural number following 9 and preceding 11. Ten is the base of the decimal numeral system, the most common system of denoting numbers in both spoken and written language.

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

In recreational mathematics, a repdigit or sometimes monodigit is a natural number composed of repeated instances of the same digit in a positional number system. The word is a portmanteau of "repeated" and "digit". Examples are 11, 666, 4444, and 999999. All repdigits are palindromic numbers and are multiples of repunits. Other well-known repdigits include the repunit primes and in particular the Mersenne primes.

In number theory, a weird number is a natural number that is abundant but not semiperfect. In other words, the sum of the proper divisors of the number is greater than the number, but no subset of those divisors sums to the number itself.

In mathematics, a Riesel number is an odd natural number k for which $is composite for all natural numbers n . In other words, when k is a Riesel number, all members of the following set are composite:$

23 (twenty-three) is the natural number following 22 and preceding 24.

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

35 (thirty-five) is the natural number following 34 and preceding 36.

The AKS primality test is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

1000 or one thousand is the natural number following 999 and preceding 1001. In most English-speaking countries, it can be written with or without a comma or sometimes a period separating the thousands digit: 1,000.

144 is the natural number following 143 and preceding 145.

Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.

In number theory, friendly numbers are two or more natural numbers with a common abundancy index, the ratio between the sum of divisors of a number and the number itself. Two numbers with the same "abundancy" form a friendly pair; n numbers with the same "abundancy" form a friendly n-tuple.

5 (five) is a number, numeral and digit. It is the natural number, and cardinal number, following 4 and preceding 6, and is a prime number.

A double exponential function is a constant raised to the power of an exponential function. The general formula is $(where a >1 and b >1), which grows much more quickly than an exponential function. For example, if a = b = 10:$

In number theory, a prime $k$ -tuple is a finite collection of values representing a repeatable pattern of differences between prime numbers. For a $k$ -tuple $(a, b, \dots)$ , the positions where the $k$ -tuple matches a pattern in the prime numbers are given by the set of integers $n$ such that all of the values $(n + a, n + b, \dots)$ are prime. Typically the first value in the $k$ -tuple is 0 and the rest are distinct positive even numbers.

In mathematics, the n-th hyperharmonic number of order r, denoted by $, is recursively defined by the relations:$

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, JSTOR 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.
↑ Wang, Venecia (October 2012), "A counterexample to the prime conjecture of expressing numbers using just ones", Journal of Number Theory, 133 (2), JNT: 391–397, doi: 10.1016/j.jnt.2012.08.003 .

External links

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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, JSTOR 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.

[6] Wang, Venecia (October 2012), "A counterexample to the prime conjecture of expressing numbers using just ones", Journal of Number Theory, 133 (2), JNT: 391–397, doi: 10.1016/j.jnt.2012.08.003 .

[1]

[2]

[3]

[4]

[5]

[6]