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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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. 3
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: A270432 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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 7 11:14 EST 2016. Contains 278871 sequences.