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
editFor 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
The smallest numbers with complexity 1, 2, 3, ... are
Upper and lower bounds
editThe 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
For example, when k = 10, x = 2 and the largest integer that can be expressed using ten ones is 22 32 = 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 log3 n. The complexity of n is at most 3 log2 n (approximately 4.755 log3 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 log3 n.[3]
Algorithms and counterexamples
editThe complexity of every integer n up to some threshold N can be calculated in total time O(N 1.222911236).[4]. This was improved to time algorithm by He[5]. The complexity of a single integer can also be computed in sublinear time of .
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.[6] In fact, one can show that . Moreover, Venecia Wang gave some interesting examples, i.e. , , , but .[7]
References
edit- ^ 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
- ^ He, Qizheng (2023), Improved Algorithms for Integer Complexity, arXiv:2308.10301, doi:10.48550/arXiv.2308.10301
- ^ 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.
