1,2

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 allows juxtaposition of 1's to form larger integers, so, for example, 2 = 1+1 has complexity 2, but unlike A003037, so does 11 = 1#1 (concatenating two 1's is an allowed operation). Similarly a(111)= 3. The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

An example (usually nonunique) of the derivation of the first 24 values.

a(1) = 1, the number of 1's in "1."

a(2) = 2, the number of 1's in "1+1 = 2."

a(3) = 3, the number of 1's in "1+1+1 = 3."

a(4) = 4, the number of 1's in "1+1+1+1 = 4."

a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."

a(6) = 5, since there are 5 1's in "((1+1)*(1+1+1)) = 6."

a(7) = 6, since there are 6 1's in "1+(((1+1)*(1+1+1))) = 7."

a(8) = 5, since there are 5 1's in "(1+1)^(1+1+1) = 8."

a(9) = 5, since there are 5 1's in "(1+1+1)^(1+1) = 9."

a(10) = 6 since there are 6 1's in "1+((1+1+1)^(1+1)) = ten.

a(11) = 2 since there are 2 1's in "1#1 = eleven."

a(12) = 3 since there are 3 1's in "1+(1#1) = twelve."

a(13) = 4 since there are 4 1's in "1+1+(1#1) = thirteen."

a(14) = 5 since there are 5 1's in "1+1+1+(1#1) = fourteen."

a(16) = 6 since there are 6 1's in "(1+1+1+1)^(1+1)."

a(17) = 7 since there are 7 1's in "1+((1+1+1+1)^(1+1))."

a(18) = 7 since there are 7 1's in "(1+1)*((1+1+1)^(1+1))."

a(19) = 7 since there are 7 1's in "(1#1)+((1+1)^(1+1+1))."

a(20) = 7 since there are 7 1's in "(1#1)+((1+1+1)^(1+1))."

a(21) = 8 since there are 8 1's in "1+((1#1)+((1+1+1)^(1+1)))."

a(22) = 4 since 22 = (1+1)*(1#1) = (1#1)+(1#1) = (1#1)#(1#1).

Cf. A003037, A025280, A005520, A005245, A005421, A117618.

Adjacent sequences: A133341 A133342 A133343 this_sequence A133345 A133346 A133347

Sequence in context: A081610 A063273 A007599 this_sequence A091334 A025280 A096365

base,nonn

Jonathan Vos Post (jvospost2(AT)yahoo.com), Oct 20 2007