login
A274061
Number of 1's required to build n using +, * and concatenation of 1's, where the result of concatenation is interpreted as a binary string.
1
1, 2, 2, 3, 4, 4, 3, 4, 4, 5, 6, 5, 6, 5, 4, 5, 6, 6, 7, 7, 5, 6, 7, 6, 7, 8, 6, 6, 7, 6, 5, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 7, 8, 8, 6, 7, 8, 7, 6, 7, 8, 8, 9, 8, 9, 7, 8, 9, 9, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8, 9, 10, 8, 9, 9, 10, 11, 9, 8, 9, 10, 8, 9, 10, 9, 9, 10, 8, 9, 9, 7, 8, 9, 8, 9, 8, 9, 9
OFFSET
1,2
COMMENTS
Like A005245, but concatenation of ones is allowed and their results are treated as binary representations of integers. Hence 3 can be represented as 11, 7 as 111 and so on.
The largest number with complexity n is 2^n-1 (A000225), the concatenation of n 1's. This follows from (2^m-1)(2^n-1) < 2^(m+n)-1 for m, n >= 1.
LINKS
EXAMPLE
n . minimal expression . number of 1's
1...1....................1
2...1+1..................2
3...11...................2
4...11+1.................3
5...11+1+1...............4
6...11*(1+1).............4
7...111..................3
8...111+1................4
9...11*11................4
10..11*11+1..............5
11..11*11+1+1............6
12..11*(11+1)............5
13..11*(11+1)+1..........6
14..111*(1+1)............5
15..1111.................4
16..1111+1...............5
17..1111+1+1.............6
18..11*11*(1+1)..........6
19..11*11*(1+1)+1........7
20..(11+1+1)(11+1).......7
21..111*11...............5
MAPLE
with(numtheory):
a:= proc(n) option remember; (k-> `if`(2^k=n+1, k,
min(seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
seq(a(i)+a(n-i), i=1..n/2))))(ilog2(n+1))
end:
seq(a(n), n=1..120); # Alois P. Heinz, Jun 09 2016
MATHEMATICA
a[n_] := a[n] = Function[k, If[2^k == n+1, k, Min[Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}], Table[a[i] + a[n-i], {i, 1, n/2}]]]] @ Floor[Log[2, n+1]];
Array[a, 100] (* Jean-François Alcover, Mar 27 2017, after Alois P. Heinz *)
CROSSREFS
Sequence in context: A325954 A243503 A069581 * A284009 A339695 A326846
KEYWORD
nonn
AUTHOR
Jeremy Tan, Jun 08 2016
STATUS
approved