

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^n1 (A000225), the concatenation of n 1's. This follows from (2^m1)(2^n1) < 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(ni), 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[ni], {i, 1, n/2}]]]] @ Floor[Log[2, n+1]];
Array[a, 100] (* JeanFrançois Alcover, Mar 27 2017, after Alois P. Heinz *)


CROSSREFS

Cf. A005245, A133344.
Sequence in context: A325954 A243503 A069581 * A284009 A326846 A243220
Adjacent sequences: A274058 A274059 A274060 * A274062 A274063 A274064


KEYWORD

nonn


AUTHOR

Jeremy Tan, Jun 08 2016


STATUS

approved



