Integer complexity

Last updated January 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

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number $, which in modular arithmetic satisfies the congruence relation:$

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 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.

A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or $(41, 43)$ . In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair.

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.

<span class="mw-page-title-main">Euler's constant</span> Constant value used in mathematics

Euler's constant is a mathematical constant, usually denoted by the lowercase Greek letter gamma, defined as the limiting difference between the harmonic series and the natural logarithm, denoted here by $log$ :

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 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.

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

A powerful number is a positive integer m such that for every prime number p dividing m, p² also divides m. Equivalently, a powerful number is the product of a square and a cube, that is, a number m of the form m = a²b³, where a and b are positive integers. Powerful numbers are also known as squareful, square-full, or 2-full. Paul Erdős and George Szekeres studied such numbers and Solomon W. Golomb named such numbers powerful.

In mathematics, a covering system is a collection

The Beal conjecture is the following conjecture in number theory:

A Markov number or Markoff number is a positive integer x, y or z that is part of a solution to the Markov Diophantine equation

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. It has garnered attention throughout history in part because distal extremities in humans typically contain five digits.

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 number theory, primes in arithmetic progression are any sequence of at least three prime numbers that are consecutive terms in an arithmetic progression. An example is the sequence of primes, which is given by $for .$

In number theory, the multiplicative digital root of a natural number $in a given number base is found by multiplying the digits of together, then repeating this operation until only a single-digit remains, which is called the multiplicative digital root of . The multiplicative digital root for the first few positive integers are:$

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, JNT, 133 (2): 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, JNT, 133 (2): 391–397, doi: 10.1016/j.jnt.2012.08.003 .

[1]

[2]

[3]

[4]

[5]

[6]