Complexity (Number)
The number of 1s needed to represent an Integer using only additions, multiplications, and parentheses arecalled the integer's complexity. For example,
So, for the first few
, 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. SequenceA005245/M0457in ``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.