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, 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

Author

Jeremy Tan, Jun 08 2016

Keywords

• nonn

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.

Examples

			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
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000
• Jeremy Tan, Python program

Crossrefs

Cf. A005245, A133344.

Programs

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 *)