Complexity (Number)

The number of 1s needed to represent an Integer using only additions, multiplications, and parentheses are called the integer's complexity. For example,

$$\begin{eqnarray*} 1&=&1\\ 2&=&1+1\\ 3&=&1+1+1\\ 4&=&(1+1)(1+1)=1+1+1+1\\ ... ...&(1+1+1)(1+1+1)\\ 10&=&(1+1+1)(1+1+1)+1\\ &=&(1+1)(1+1+1+1+1) \end{eqnarray*}$$

So, for the first few $n$, the complexity is 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, ... (Sloane's A005245).

References

Guy, R. K. ``Expressing Numbers Using Just Ones.'' §F26 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 263, 1994.

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.

Rawsthorne, D. A. ``How Many 1's are Needed?'' Fib. Quart. 27, 14-17, 1989.

Sloane, N. J. A. Sequence A005245/M0457 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.