For instance, the number 11 may be represented using eight ones: However, it has no representation using seven or fewer ones.
The complexities of the numbers 1, 2, 3, ... are The smallest numbers with complexity 1, 2, 3, ... are 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 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 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] The complexities of all integers up to some threshold N can be calculated in total time O(N 1.222911236).
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.
Moreover, Venecia Wang gave some interesting examples, i.e.