|
|
A003037
|
|
Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.
(Formerly M0527)
|
|
14
|
|
|
1, 2, 3, 4, 5, 7, 11, 13, 21, 23, 41, 43, 71, 94, 139, 211, 215, 431, 863, 1437, 1868, 2855, 5737, 8935, 15838, 15839, 54357, 95597, 139117, 233195, 470399, 1228247, 2183791, 4388063, 6945587, 13431919, 32329439, 46551023
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications, exponentiation and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not (concatenating two 1's is not an allowed operation). The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions. - Jonathan Vos Post, Oct 20 2007
|
|
REFERENCES
|
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
|
|
EXAMPLE
|
An example (usually nonunique) of the derivation of the first 10 values.
a(1) = 1, the number of 1's in "1."
a(2) = 2, the number of 1's in "1+1 = 2."
a(3) = 3, the number of 1's in "1+1+1 = 3."
a(4) = 4, the number of 1's in "1+1+1+1 = 4."
a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
a(6) = 7, since there are 6 1's in "((1+1)*(1+1+1))+1 = 7."
a(7) = 11, since there are 7 1's in "((1+1+1)^(1+1))+1+1 = eleven."
a(8) = 13, since there are 8 1's in "((1+1+1)*(1+1+1+1))+1 = thirteen."
a(9) = 21, since there are 9 1's in "((1+1+1)*(((1+1)*(1+1+1))+1) = twenty-one."
a(10) = 23, since there are 10 1's in "1+((1+1)*(((1+1+1)^(1+1))+1+1)) = twenty-three."
|
|
MAPLE
|
xmax:= 5: # get terms <= 10^xmax
C[1]:= {1}: A[1]:= 1: CU[1]:= {1}:
for n from 2 do
C[n]:= {seq(seq(seq(op(select(`<=`,
[a+b, a*b, `if`(b*ilog10(a) <= xmax, a^b, NULL), `if`(a*ilog10(b) <= xmax, b^a, NULL)]
, 10^xmax)), b=C[n-k]), a=C[k]), k=1..floor(n/2))}
minus CU[n-1];
if C[n] = {} then break fi;
A[n]:= min(C[n]);
CU[n]:= CU[n-1] union C[n];
od:
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|