|
%I M0527 #37 Jun 09 2017 23:37:54
%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
|
