login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003037 Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.
(Formerly M0527)
13
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

Table of n, a(n) for n=1..38.

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

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:

seq(A[i], i=1..n-1); # Robert Israel, Jan 08 2015

CROSSREFS

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

Sequence in context: A174291 A007885 A192586 * A259466 A046420 A108318

Adjacent sequences:  A003034 A003035 A003036 * A003038 A003039 A003040

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson, May 15 1997

More terms from Sean A. Irvine, Jan 07 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 10 18:10 EST 2019. Contains 329901 sequences. (Running on oeis4.)