|
| |
|
|
A133344
|
|
Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.
|
|
5
|
|
|
|
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
|
|
|
|
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:
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
