Английская Википедия:Integer complexity
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, ... Шаблон:OEIS
The smallest numbers with complexity 1, 2, 3, ... are
- 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... Шаблон:OEIS
Upper and lower bounds
The question of expressing integers in this way was originally considered by Шаблон:Harvtxt. They asked for the largest number with a given complexity Шаблон:Mvar;[1] later, Selfridge showed that this number is
- <math>2^x3^{(k-2x)/3} \text{ where } x = -k\bmod 3.</math>
For example, when Шаблон:Math, Шаблон:Math and the largest integer that can be expressed using ten ones is Шаблон:Math. Its expression is
- (1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).
Thus, the complexity of an integer Шаблон:Mvar is at least Шаблон:Math. The complexity of Шаблон:Mvar is at most Шаблон:Math (approximately Шаблон:Math): an expression of this length for Шаблон:Mvar can be found by applying Horner's method to the binary representation of Шаблон:Mvar.[2] Almost all integers have a representation whose length is bounded by a logarithm with a smaller constant factor, Шаблон:Math.[3]
Algorithms and counterexamples
The complexities of all integers up to some threshold Шаблон:Mvar can be calculated in total time Шаблон:Math.[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 Шаблон:Mvar is obtained either by subtracting one from Шаблон:Mvar or by expressing Шаблон:Mvar 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 Шаблон:Mvar is one plus the complexity of Шаблон:Math.[5] In fact, one can show that <math>\|p\| = \|p-1\| = 63</math>. Moreover, Venecia Wang gave some interesting examples, i.e. <math>\|743 \times 2\| = \|743\| = 22</math>, <math>\|166571 \times 3\| = \|166571\| = 39</math>, <math>\|97103 \times 5\| = \|97103\| = 38</math>, <math>\|23^2\| = 20</math> but <math>2 \|23\| = 22</math>.[6]
References
External links
