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
Alois P. Heinz, Table of n, a(n) for n = 1..20000
Jeremy Tan, Python program
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
KEYWORD
nonn
AUTHOR
Jeremy Tan, Jun 08 2016
STATUS
approved