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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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 December 18 19:05 EST 2014. Contains 252174 sequences.