A003037 Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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

Examples

			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 = 11."
a(8) = 13, since there are 8 1's in "((1+1+1)*(1+1+1+1))+1 = 13."
a(9) = 21, since there are 9 1's in "(1+1+1)*(((1+1)*(1+1+1))+1) = 21."
a(10) = 23, since there are 10 1's in "1+((1+1)*(((1+1+1)^(1+1))+1+1)) = 23."
		

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, Letter to N. J. A. Sloane, 1980
• 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]
• Index to sequences related to the complexity of n

Crossrefs

Cf. A025280, A005520, A005245, A005421, A117618.

Programs

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:
seq(A[i],i=1..n-1); # Robert Israel, Jan 08 2015

Extensions

More terms from David W. Wilson, May 15 1997

More terms from Sean A. Irvine, Jan 07 2015