TOPICS
Search

Integer Complexity

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ComplexityNumber

The complexity c_n of an integer n is the least number of 1s needed to represent it using only additions, multiplications, and parentheses. For example, the numbers 1 through 10 can be minimally represented as

1=1
(1)
2=1+1
(2)
3=1+1+1
(3)
4=(1+1)(1+1)
(4)
=1+1+1+1
(5)
5=(1+1)(1+1)+1
(6)
=1+1+1+1+1
(7)
6=(1+1)(1+1+1)
(8)
7=(1+1)(1+1+1)+1
(9)
8=(1+1)(1+1)(1+1)
(10)
9=(1+1+1)(1+1+1)
(11)
10=(1+1+1)(1+1+1)+1
(12)
=(1+1)(1+1+1+1+1),
(13)

so the complexities for n=1, 2, ..., are 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, ... (OEIS A005245).

The smallest numbers of complexity n=1, 2, ... are 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, ... (OEIS A005520).

See also

Complexity

Explore with Wolfram|Alpha

References

Guy, R. K. "Some Suspiciously Simple Sequences." Amer. Math. Monthly 93, 186-190, 1986.Guy, R. K. "Monthly Unsolved Problems, 1969-1987." Amer. Math. Monthly 94, 961-970, 1987.Guy, R. K. "Unsolved Problems Come of Age." Amer. Math. Monthly 96, 903-909, 1989.Guy, R. K. "Expressing Numbers Using Just Ones." §F26 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 263, 1994.Pegg, E. Jr. "Math Games: Integer Complexity." Apr. 12, 2004. https://www.mathpuzzle.com/MAA/17-Integer%20Complexity/mathgames_04_12_04.html. Pegg, E. Jr. "Integer Complexity." https://library.wolfram.com/infocenter/MathSource/5175/.Rawsthorne, D. A. "How Many 1's Are Needed?" Fib. Quart. 27, 14-17, 1989.Sloane, N. J. A. Sequences A005245/M0457 and A005520/M0523 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 916, 2002.

Referenced on Wolfram|Alpha

Integer Complexity

Cite this as:

Weisstein, Eric W. "Integer Complexity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IntegerComplexity.html

Subject classifications