cp's OEIS Frontend

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

%I A003037 M0527 #41 Aug 01 2024 03:10:27
%S A003037 1,2,3,4,5,7,11,13,21,23,41,43,71,94,139,211,215,431,863,1437,1868,
%T A003037 2855,5737,8935,15838,15839,54357,95597,139117,233195,470399,1228247,
%U A003037 2183791,4388063,6945587,13431919,32329439,46551023
%N A003037 Smallest number of complexity n: smallest number requiring n 1's to build using +, * and ^.
%C A003037 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 A003037 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 A003037 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003037 W. A. Beyer, <a href="/A005208/a005208.pdf">Letter to N. J. A. Sloane, 1980</a>
%H A003037 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 A003037 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A003037 An example (usually nonunique) of the derivation of the first 10 values.
%e A003037 a(1) = 1, the number of 1's in "1."
%e A003037 a(2) = 2, the number of 1's in "1+1 = 2."
%e A003037 a(3) = 3, the number of 1's in "1+1+1 = 3."
%e A003037 a(4) = 4, the number of 1's in "1+1+1+1 = 4."
%e A003037 a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
%e A003037 a(6) = 7, since there are 6 1's in "((1+1)*(1+1+1))+1 = 7."
%e A003037 a(7) = 11, since there are 7 1's in "((1+1+1)^(1+1))+1+1 = 11."
%e A003037 a(8) = 13, since there are 8 1's in "((1+1+1)*(1+1+1+1))+1 = 13."
%e A003037 a(9) = 21, since there are 9 1's in "(1+1+1)*(((1+1)*(1+1+1))+1) = 21."
%e A003037 a(10) = 23, since there are 10 1's in "1+((1+1)*(((1+1+1)^(1+1))+1+1)) = 23."
%p A003037 xmax:= 5:  # get terms <= 10^xmax
%p A003037 C[1]:= {1}: A[1]:= 1: CU[1]:= {1}:
%p A003037 for n from 2 do
%p A003037    C[n]:= {seq(seq(seq(op(select(`<=`,
%p A003037 [a+b,a*b,`if`(b*ilog10(a) <= xmax,a^b,NULL),`if`(a*ilog10(b) <= xmax,b^a,NULL)]
%p A003037          ,10^xmax)),b=C[n-k]),a=C[k]),k=1..floor(n/2))}
%p A003037          minus CU[n-1];
%p A003037    if C[n] = {} then break fi;
%p A003037    A[n]:= min(C[n]);
%p A003037    CU[n]:= CU[n-1] union C[n];
%p A003037 od:
%p A003037 seq(A[i],i=1..n-1); # _Robert Israel_, Jan 08 2015
%Y A003037 Cf. A025280, A005520, A005245, A005421, A117618.
%K A003037 nonn,nice
%O A003037 1,2
%A A003037 _N. J. A. Sloane_
%E A003037 More terms from _David W. Wilson_, May 15 1997
%E A003037 More terms from _Sean A. Irvine_, Jan 07 2015