info prev up next book cdrom email home

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.




© 1996-9 Eric W. Weisstein
1999-05-26