This site is supported by donations to The OEIS Foundation. 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!)
 A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *. (Formerly M0523) 29
 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467, 683, 719, 1223, 1438, 1439, 2879, 3767, 4283, 6299, 10079, 11807, 15287, 21599, 33599, 45197, 56039, 81647, 98999, 163259, 203999, 241883, 371447, 540539, 590399, 907199 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Ed Pegg Jr, www.mathpuzzle.com, Apr 10 2001, notes that all the new terms are -1 mod 120. - That is, this holds at least for all terms from a(45) = 590399 up to the highest known term a(89) given in the b-file at the end of 2015. Comment clarified by Antti Karttunen, Dec 14 2015 Largest number of complexity n is given by A000792. - David W. Wilson, Oct 03 2005 After 1438 = 2 * 719, all elements through 8206559 are primes. Equivalently, except for a(4) = 4, a(7) = 10, a(10) = 22 and a(25) = 1438, we have a(1) through a(53) are all primes. - Jonathan Vos Post, Apr 07 2006 a(54)-a(89) are all primes. - Janis Iraids, Apr 21 2011 Previous observations (primes with property -1 mod 120) still hold. - Martins Opmanis, Oct 16 2009 The prime 353942783 = A189125(1) = 2*3 + (1 + 2^2*3^2)*(2 + 3^4(1 + 2*3^10)) is the smallest counterexample to Guy's first hypothesis on integer complexity. - Jonathan Vos Post, Mar 30 2012 The sequence A265360 (second smallest number of complexity n) seems to have similar properties. - Janis Iraids via Antti Karttunen, Dec 15 2015 REFERENCES R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Janis Iraids, Table of n, a(n) for n = 1..89 J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission] J. Arias de Reyna, J. van de Lune, The question "How many 1's are needed?" revisited, arXiv preprint arXiv:1404.1850 [math.NT], 2014. Jānis Iraids, Kaspars Balodis, Juris Čerņenoks, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer complexity: experimental and analytical results, arXiv:1203.6462 [math.NT], 2012. Ed Pegg Jr., Math Games: Integer Complexity, www.mathpuzzle.com, April 12, 2004. D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27 (1989), 14-17. Eric Weisstein's World of Mathematics, Integer Complexity EXAMPLE Examples from Piotr Fabian: 1 = 1, 1 "one": first 1, a(1) = 1 2 = 1+1, 2 "ones": first 2, a(2) = 2 3 = 1+1+1, 3 "ones": first 3, a(3) = 3 4 = 1+1+1+1, 4 "ones": first 4, a(4) = 4 5 = 1+1+1+1+1, 5 "ones": first 5, a(5) = 5 6 = (1+1)*(1+1+1), 5 "ones" 7 = 1+((1+1)*(1+1+1)), 6 "ones": first 6, a(6) = 7 8 = (1+1)*(1+1+1+1), 6 "ones" 9 = (1+1+1)*(1+1+1), 6 "ones" 10 = 1+((1+1+1)*(1+1+1)), 7 "ones": first 7, a(7) = 10 11 = 1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, a(8) = 11 12 = (1+1)*((1+1)*(1+1+1)), 7 "ones" MAPLE N:= 100000: # to get all terms <= N R:= Vector(N): R:= 1: A:= 1: for n from 2 to N do   inds:= [seq(n-i, i=1..floor(n/2))];   m:= min(R[1..floor(n/2)] + R[inds]);   for d in select(`<=`, numtheory:-divisors(n), floor(sqrt(n))) minus {1} do     m:= min(m, R[d]+R[n/d])   od;   R[n]:= m;   if not assigned(A[m]) then A[m]:= n fi; od: seq(A[m], m=1..max(R)); # Robert Israel, Dec 14 2015 MATHEMATICA nn = 10000; R = Table[0, nn]; R[] = 1; Clear[A]; A = 1; For[n = 2, n <= nn, n++,   inds = Table[n-i, {i, 1, n/2}];   m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];   Do[     m = Min[m, R[[d]] + R[[n/d]]], {d,     Select[Rest[Divisors[n]], # <= Sqrt[n]&]}   ];   R[[n]] = m;   If[!IntegerQ[A[m]], A[m] = n]; ]; Table[A[m], {m, 1, Max[R]}] (* Jean-François Alcover, Aug 05 2018, after Robert Israel *) PROG See the Python program by Tim Peters at A005421. (MATLAB) N = 10^6; fact = cell(1, N); for n = 2:sqrt(N)   for m = [n^2:n:N]     fact{m} = [fact{m}, n];   end end R = zeros(1, N); R(1) = 1; A(1) = 1; mmax = 1; for n = 2:N   m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));   if numel(fact{n}) > 0     m = min(m, min(R(fact{n}) + R(n ./ fact{n})));   end   R(n) = m;   if m > mmax     A(m) = n;     mmax = m;   elseif A(m) == 0     A(m) = n;   end end A % Robert Israel, Dec 14 2015 CROSSREFS Cf. A005245, A025280, A003037, A005421, A048183, A181898, A182061, A265360. Sequence in context: A133493 A265938 A182061 * A048183 A255641 A122975 Adjacent sequences:  A005517 A005518 A005519 * A005521 A005522 A005523 KEYWORD nonn,nice AUTHOR EXTENSIONS Corrected and extended by David W. Wilson, May 1997 Extended to terms a(40)=163259 and a(41)=203999 by John W. Layman, Nov 03 1999 Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001 a(68)-a(89) from Janis Iraids, Apr 20 2011 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.

Last modified December 15 17:42 EST 2019. Contains 330000 sequences. (Running on oeis4.)