# Integer complexity

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Integer_complexity
> Markdown URL: https://mediated.wiki/source/Integer_complexity.md
> Source: https://en.wikipedia.org/wiki/Integer_complexity
> Source revision: 1347243467
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Length of expression as combination of 1s

In [number theory](/source/Number_theory), the **complexity of an integer** is the smallest number of [ones](/source/1_(number)) that can be used to represent it using ones and any number of [additions](/source/Addition), [multiplications](/source/Multiplication), and parentheses. It is always within a constant factor of the [logarithm](/source/Logarithm) of the given [integer](/source/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](https://oeis.org/A005245) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences))

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

- 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (sequence [A005520](https://oeis.org/A005520) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences))

## Upper and lower bounds

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

- 2 x 3 ( k − 2 x ) / 3 where x = − k mod 3 . {\displaystyle 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 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](/source/Horner's_method) to the [binary representation](/source/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

The complexity ‖ n ‖ {\displaystyle \|n\|} of every integer n up to some threshold N can be calculated in total time *O*(*N* 1.222911236).[4]. This was improved to O ( n log O ( 1 ) ⁡ n ) {\displaystyle O(n\log ^{O(1)}n)} time algorithm by He[5]. The complexity of a single integer n {\displaystyle n} can also be computed in sublinear time of O ( n 0.6514 ) {\displaystyle O(n^{0.6514})} .

Algorithms for computing the integer complexity have been used to disprove several [conjectures](/source/Conjecture) 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](/source/Prime_number), and therefore also disproves a conjecture of [Richard K. Guy](/source/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 ‖ 353942783 ‖ = ‖ 353942782 ‖ = 63 {\displaystyle \|353942783\|=\|353942782\|=63} . Moreover, Venecia Wang gave some interesting examples, i.e. ‖ 743 × 2 ‖ = ‖ 743 ‖ = 22 {\displaystyle \|743\times 2\|=\|743\|=22} , ‖ 166571 × 3 ‖ = ‖ 166571 ‖ = 39 {\displaystyle \|166571\times 3\|=\|166571\|=39} , ‖ 97103 × 5 ‖ = ‖ 97103 ‖ = 38 {\displaystyle \|97103\times 5\|=\|97103\|=38} , ‖ 23 2 ‖ = 20 {\displaystyle \|23^{2}\|=20} but 2 ‖ 23 ‖ = 22 {\displaystyle 2\|23\|=22} .[7]

## References

1. **[^](#cite_ref-1)** [Mahler, K.](/source/Kurt_Mahler); Popken, J. (1953), "On a maximum problem in arithmetic", *Nieuw Archief voor Wiskunde*, **1**: 1–15, [MR](/source/MR_(identifier)) [0053986](https://mathscinet.ams.org/mathscinet-getitem?mr=0053986).

1. **[^](#cite_ref-guy_2-0)** [Guy, Richard K.](/source/Richard_K._Guy) (1986), "Some suspiciously simple sequences", Unsolved Problems, *[American Mathematical Monthly](/source/American_Mathematical_Monthly)*, **93** (3): 186–190, [doi](/source/Doi_(identifier)):[10.2307/2323338](https://doi.org/10.2307%2F2323338), [JSTOR](/source/JSTOR_(identifier)) [2323338](https://www.jstor.org/stable/2323338), [MR](/source/MR_(identifier)) [1540817](https://mathscinet.ams.org/mathscinet-getitem?mr=1540817).

1. **[^](#cite_ref-3)** Shriver, Christopher E. (2015), *Applications of Markov chain analysis to integer complexity*, [arXiv](/source/ArXiv_(identifier)):[1511.07842](https://arxiv.org/abs/1511.07842), [Bibcode](/source/Bibcode_(identifier)):[2015arXiv151107842S](https://ui.adsabs.harvard.edu/abs/2015arXiv151107842S).

1. **[^](#cite_ref-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](/source/ArXiv_(identifier)):[1706.08424](https://arxiv.org/abs/1706.08424), [Bibcode](/source/Bibcode_(identifier)):[2017arXiv170608424C](https://ui.adsabs.harvard.edu/abs/2017arXiv170608424C)

1. **[^](#cite_ref-5)** He, Qizheng (2023), *Improved Algorithms for Integer Complexity*, [arXiv](/source/ArXiv_(identifier)):[2308.10301](https://arxiv.org/abs/2308.10301), [doi](/source/Doi_(identifier)):[10.48550/arXiv.2308.10301](https://doi.org/10.48550%2FarXiv.2308.10301)

1. **[^](#cite_ref-6)** Fuller, Martin N. (February 1, 2008), [*Program to calculate A005245, A005520, A005421*](https://oeis.org/A005245/a005245.c.txt), OEIS, retrieved 2015-12-13.

1. **[^](#cite_ref-7)** 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](/source/Doi_(identifier)):[10.1016/j.jnt.2012.08.003](https://doi.org/10.1016%2Fj.jnt.2012.08.003).

## External links

- [Weisstein, Eric W.](/source/Eric_W._Weisstein) ["Integer Complexity"](https://mathworld.wolfram.com/IntegerComplexity.html). *[MathWorld](/source/MathWorld)*.

---
Adapted from the Wikipedia article [Integer complexity](https://en.wikipedia.org/wiki/Integer_complexity) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Integer_complexity?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.