login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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

%I M0527

%S 1,2,3,4,5,7,11,13,21,23,41,43,71,94,139,211,215,431,863,1437,1868,

%T 2855,5737,8935,15838,15839,54357,95597,139117,233195,470399,1228247,

%U 2183791,4388063,6945587,13431919,32329439,46551023

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

%C 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

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H W. A. Beyer, <a href="/A005208/a005208.pdf">Letter to N. J. A. Sloane, 1980</a>

%H W. A. Beyer, M. L. Stein and S. M. Ulam, <a href="/A003037/a003037.pdf">The Notion of Complexity</a>. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%e An example (usually nonunique) of the derivation of the first 10 values.

%e a(1) = 1, the number of 1's in "1."

%e a(2) = 2, the number of 1's in "1+1 = 2."

%e a(3) = 3, the number of 1's in "1+1+1 = 3."

%e a(4) = 4, the number of 1's in "1+1+1+1 = 4."

%e a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."

%e a(6) = 7, since there are 6 1's in "((1+1)*(1+1+1))+1 = 7."

%e a(7) = 11, since there are 7 1's in "((1+1+1)^(1+1))+1+1 = eleven."

%e a(8) = 13, since there are 8 1's in "((1+1+1)*(1+1+1+1))+1 = thirteen."

%e a(9) = 21, since there are 9 1's in "((1+1+1)*(((1+1)*(1+1+1))+1) = twenty-one."

%e a(10) = 23, since there are 10 1's in "1+((1+1)*(((1+1+1)^(1+1))+1+1)) = twenty-three."

%p xmax:= 5: # get terms <= 10^xmax

%p C[1]:= {1}: A[1]:= 1: CU[1]:= {1}:

%p for n from 2 do

%p C[n]:= {seq(seq(seq(op(select(`<=`,

%p [a+b,a*b,`if`(b*ilog10(a) <= xmax,a^b,NULL),`if`(a*ilog10(b) <= xmax,b^a,NULL)]

%p ,10^xmax)),b=C[n-k]),a=C[k]),k=1..floor(n/2))}

%p minus CU[n-1];

%p if C[n] = {} then break fi;

%p A[n]:= min(C[n]);

%p CU[n]:= CU[n-1] union C[n];

%p od:

%p seq(A[i],i=1..n-1); # _Robert Israel_, Jan 08 2015

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

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, May 15 1997

%E More terms from _Sean A. Irvine_, Jan 07 2015

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 January 18 16:27 EST 2020. Contains 331011 sequences. (Running on oeis4.)