login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation. 2
1, 2, 3, 4, 5, 5, 6, 5, 5, 6, 2, 3, 4, 5, 6, 6, 7, 6, 6, 7, 3, 4, 5, 5, 6, 6, 6, 7, 7, 8, 4, 5, 5, 6, 7, 6, 7, 8, 7, 8, 5, 5, 6, 6, 7, 7, 8, 7, 8, 8, 6, 7, 7, 8, 7, 8, 9, 9, 9, 8, 6, 6, 6, 7, 8, 7, 8, 8, 8, 9, 7, 8, 8, 8, 9, 10, 8, 9, 10, 10, 6, 7, 8, 7, 8, 8 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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 numbers to form larger integers, so for example, 2 = 1+1 has complexity 2, but unlike A003037, so does 11 = 1#1 (concatenating two numbers 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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Index to sequences related to the complexity of n

EXAMPLE

An example (usually nonunique) of the derivation of the first 22 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) = 6 since there are 6 1's in "1#((1+1)^(1+1+1))."

a(19) = 6 since there are 6 1's in "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) = 3 since there are 3 1's in "(1+1)#1."

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

MAPLE

with(numtheory):

a:= proc(n) option remember; local r; `if`(n=1, 1, min(

       seq(a(i)+a(n-i), i=1..n-1),

       seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),

       seq(`if`(cat("", n)[i+1]<>"0", a(iquo(n, 10^(length(n)-i),

           'r'))+a(r), NULL), i=1..length(n)-1),

       seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],

           i=ifactors(n)[2]))) minus {0, 1})))

    end:

seq(a(n), n=1..120);  # Alois P. Heinz, Nov 06 2013

CROSSREFS

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

Sequence in context: A200262 A007599 A154940 * A091334 A025280 A096365

Adjacent sequences:  A133341 A133342 A133343 * A133345 A133346 A133347

KEYWORD

base,nonn

AUTHOR

Jonathan Vos Post, Oct 20 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 23 12:19 EDT 2014. Contains 248462 sequences.