In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, the integer complexity of an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
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
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
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 eight.
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, ...
The smallest numbers with complexity 1, 2, 3, ... are
:1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ...
Upper and lower bounds
The question of expressing integers in this way was originally considered by . They asked for the largest number with a given complexity ; later, Selfridge showed that this number is
:
For example, when , and the largest integer that can be expressed using ten ones is . Its expression is
:(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).
Thus, the complexity of an integer is at least . The complexity of is at most (approximately ): an expression of this length for can be found by applying
Horner's method
In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horn ...
to the
binary representation
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
The base-2 numeral system is a positional notation ...
of .
[.] Almost all integers have a representation whose length is bounded by a logarithm with a smaller constant factor, .
Algorithms and counterexamples
The complexities of all integers up to some threshold can be calculated in total time .
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 is obtained either by subtracting one from or by expressing 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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, and therefore also disproves a conjecture of
Richard K. Guy that the complexity of every prime number is one plus the complexity of . In fact, one can show that
. Moreover, Venecia Wang gave some interesting examples, i.e.
,
,
,
but
.
[.]
References
External links
*{{mathworld, title=Integer Complexity, id=IntegerComplexity
Integer sequences