The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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,            i=ifactors(n)))) 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: A330881 A279317 A154940 * A323727 A091334 A306560 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 13 10:38 EDT 2020. Contains 335687 sequences. (Running on oeis4.)