%I A005245 M0457
%S A005245 1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,9,10,11,9,10,10,9,10,11,10,11,
%T A005245 10,11,11,11,10,11,11,11,11,12,11,12,12,11,12,13,11,12,12,12,12,13,11,
               12,
%U A005245 12,12,13,14,12,13,13,12,12,13,13,14,13,14,13,14,12,13,13,13,13,14,13,
               14
%N A005245 Complexity of n: number of 1's required to build n using + and *.
%C A005245 The complexity of an integer n is the least number of 1's needed to represent 
               it using only additions, multiplications 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 ("pasting together" two 
               1's is not an allowed operation).
%C A005245 The complexity of a number has been defined in several different ways 
               by different authors. See the Index to the OEIS for other definitions.
%D A005245 R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 
               (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%D A005245 R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
%D A005245 M. Criton, "Les uns de Germain", Problem No.4 pp 13 ; 68 in '7 x 7 Enigmes 
               Et Defis Mathematques pour tous', vol.25 Editions POLE Paris 2001. 
               [From Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 04 2009]
%D A005245 J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la 
               Real Sociedad Matematica Espanola, 3, (2000), 230-250.
%D A005245 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A005245 M. F. Hasler, <a href="b005245.txt">Table of n, a(n) for n = 1..10000</
               a>
%H A005245 Martin N. Fuller, <a href="a005245.c.txt">C program</a>
%H A005245 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               IntegerComplexity.html">Integer Complexity</a>
%F A005245 It's known that a(n)<= A061373(n) but I think 0 <= A061373(n)-a(n) <= 
               1 also holds. - Benoit Cloitre, Nov 23 2003. That's false: the numbers 
               {46, 235, 649, 1081, 7849, 31669, 61993} require {1, 2, 3, 4, 5, 
               6, 7} fewer 1's in A005245 than in A061373. - Ed Pegg Jr, Apr 13 
               2004.
%e A005245 Contribution from Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 04 2009: 
               (Start)
%e A005245 n ........... minimal expression........... a(n)= number of 1's
%e A005245 1.....................1.......................1
%e A005245 2....................1+1......................2
%e A005245 3...................1+1+1.....................3
%e A005245 4................(1+1)*(1+1)..................4
%e A005245 5...............(1+1)*(1+1)+1.................5
%e A005245 6...............(1+1)*(1+1+1).................5
%e A005245 7..............(1+1)*(1+1+1)+1................6
%e A005245 8.............(1+1)*(1+1)*(1+1)...............6
%e A005245 9..............(1+1+1)*(1+1+1)................6
%e A005245 10............(1+1+1)*(1+1+1)+1...............7
%e A005245 11...........(1+1+1)*(1+1+1)+1+1..............8
%e A005245 12...........(1+1)*(1+1)*(1+1+1)..............7
%e A005245 13..........(1+1)*(1+1)*(1+1+1)+1.............8
%e A005245 14.........{(1+1)*(1+1+1)+1}*(1+1)............8
%e A005245 15.........{(1+1)*(1+1)+1}*(1+1+1)............8
%e A005245 16.........(1+1)*(1+1)*(1+1)*(1+1)............8
%e A005245 17........(1+1)*(1+1)*(1+1)*(1+1)+1...........9
%e A005245 18..........(1+1)*(1+1+1)*(1+1+1).............8
%e A005245 19.........(1+1)*(1+1+1)*(1+1+1)+1............9
%e A005245 20........{(1+1+1)*(1+1+1)+1}*(1+1)...........9
%e A005245 21........{(1+1)*(1+1+1)+1}*(1+1+1)...........9
%e A005245 22.......{(1+1)*(1+1+1)+1}*(1+1+1)+1..........10
%e A005245 23......{(1+1)*(1+1+1)+1}*(1+1+1)+1+1.........11
%e A005245 24........(1+1)*(1+1)*(1+1)*(1+1+1)...........9
%e A005245 25.......(1+1)*(1+1)*(1+1)*(1+1+1)+1..........10
%e A005245 26......{(1+1)*(1+1)*(1+1+1)+1}*(1+1).........10
%e A005245 27.........(1+1+1)*(1+1+1)*(1+1+1)............9
%e A005245 28........(1+1+1)*(1+1+1)*(1+1+1)+1...........10
%e A005245 29.......(1+1+1)*(1+1+1)*(1+1+1)+1+1..........11
%e A005245 30.......{(1+1+1)*(1+1+1)+1}*(1+1+1)..........10
%e A005245 31......{(1+1+1)*(1+1+1)+1}*(1+1+1)+1.........11
%e A005245 32......(1+1)*(1+1)*(1+1)*(1+1)*(1+1).........10
%e A005245 33.....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)..........11
%e A005245 34...{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)........11
%e A005245 ................................................
%e A005245 (End)
%o A005245 (PARI, from M. F. Hasler, Jan 30 2008) A005245(n /* start by calling 
               this with the largest needed n */, lim/* see below */) = { local(d); 
               n<6&return(n);
%o A005245 if(n<=#A5245, A5245[n]&return(A5245[n]) /* return memoized result if 
               available */,
%o A005245 A5245=vector(n) /*create vector if needed - should better re-use exiting 
               data if available */);
%o A005245 for(i=1, n-1, A5245[i] | A5245[i]=A005245(i,lim)); /* compute all previous 
               elements */
%o A005245 A5245[n]=min( vecmin(vector(min(n\2,if(lim>0,lim,n)), k, A5245[k]+A5245[n-k])) 
               /* additive possibilities - if lim>0 is given, consider a(k)+a(n-k) 
               only for k<=lim - we know it is save to use lim=1 up to n=2e7 */, 
               if( isprime(n), n, vecmin(vector((-1+#d=divisors(n))\2, i, A5245[d[i+1]]+A5245[d[ 
               #d-i]]))/* multiplicative possibilities */))}
%o A005245 See also the Python program by Tim Peters at A005421.
%Y A005245 Cf. A000792 (largest integer of given complexity).
%Y A005245 Cf. A003313, A076142, A076091, A061373, A005421, A064097.
%Y A005245 Cf. A005520, A025280, A003037.
%Y A005245 Sequence in context: A096365 A007600 A091333 this_sequence A061373 A104135 
               A046108
%Y A005245 Adjacent sequences: A005242 A005243 A005244 this_sequence A005246 A005247 
               A005248
%K A005245 nonn,nice
%O A005245 1,2
%A A005245 N. J. A. Sloane (njas(AT)research.att.com).
%E A005245 More terms from David W. Wilson (davidwwilson(AT)comcast.net) May 15 
               1997