1,2

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).

The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

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

R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

J. Arias de Reyna, Complejidad de los numeros naturales, Gaceta de la Real Sociedad Matematica Espanola, 3, (2000), 230-250.

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]

M. F. Hasler, Table of n, a(n) for n = 1..10000

Martin N. Fuller, C program

Eric Weisstein's World of Mathematics, Integer Complexity

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.

Contribution from Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 04 2009: (Start)

n ........... minimal expression........... a(n)= number of 1's

1.....................1.......................1

2....................1+1......................2

3...................1+1+1.....................3

4................(1+1)*(1+1)..................4

5...............(1+1)*(1+1)+1.................5

6...............(1+1)*(1+1+1).................5

7..............(1+1)*(1+1+1)+1................6

8.............(1+1)*(1+1)*(1+1)...............6

9..............(1+1+1)*(1+1+1)................6

10............(1+1+1)*(1+1+1)+1...............7

11...........(1+1+1)*(1+1+1)+1+1..............8

12...........(1+1)*(1+1)*(1+1+1)..............7

13..........(1+1)*(1+1)*(1+1+1)+1.............8

14.........{(1+1)*(1+1+1)+1}*(1+1)............8

15.........{(1+1)*(1+1)+1}*(1+1+1)............8

16.........(1+1)*(1+1)*(1+1)*(1+1)............8

17........(1+1)*(1+1)*(1+1)*(1+1)+1...........9

18..........(1+1)*(1+1+1)*(1+1+1).............8

19.........(1+1)*(1+1+1)*(1+1+1)+1............9

20........{(1+1+1)*(1+1+1)+1}*(1+1)...........9

21........{(1+1)*(1+1+1)+1}*(1+1+1)...........9

22.......{(1+1)*(1+1+1)+1}*(1+1+1)+1..........10

23......{(1+1)*(1+1+1)+1}*(1+1+1)+1+1.........11

24........(1+1)*(1+1)*(1+1)*(1+1+1)...........9

25.......(1+1)*(1+1)*(1+1)*(1+1+1)+1..........10

26......{(1+1)*(1+1)*(1+1+1)+1}*(1+1).........10

27.........(1+1+1)*(1+1+1)*(1+1+1)............9

28........(1+1+1)*(1+1+1)*(1+1+1)+1...........10

29.......(1+1+1)*(1+1+1)*(1+1+1)+1+1..........11

30.......{(1+1+1)*(1+1+1)+1}*(1+1+1)..........10

31......{(1+1+1)*(1+1+1)+1}*(1+1+1)+1.........11

32......(1+1)*(1+1)*(1+1)*(1+1)*(1+1).........10

33.....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)..........11

34...{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)........11

................................................

(End)

(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);

if(n<=#A5245, A5245[n]&return(A5245[n]) /* return memoized result if available */,

A5245=vector(n) /*create vector if needed - should better re-use exiting data if available */);

for(i=1, n-1, A5245[i] | A5245[i]=A005245(i, lim)); /* compute all previous elements */

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 */))}

See also the Python program by Tim Peters at A005421.

Cf. A000792 (largest integer of given complexity).

Cf. A003313, A076142, A076091, A061373, A005421, A064097.

Cf. A005520, A025280, A003037.

Adjacent sequences: A005242 A005243 A005244 this_sequence A005246 A005247 A005248

Sequence in context: A096365 A007600 A091333 this_sequence A061373 A104135 A046108

nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from David W. Wilson (davidwwilson(AT)comcast.net) May 15 1997