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

Cf. A005245, A133344.

Sequence in context: A325954 A243503 A069581 * A284009 A339695 A326846

Adjacent sequences: A274058 A274059 A274060 * A274062 A274063 A274064

Keyword

nonn

Author

Jeremy Tan, Jun 08 2016

Status

approved