|
%I #16 Mar 27 2017 07:46:07
%S 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,
%T 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,
%U 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
%N 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.
%C 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.
%C 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.
%H Alois P. Heinz, <a href="/A274061/b274061.txt">Table of n, a(n) for n = 1..20000</a>
%H Jeremy Tan, <a href="https://gist.github.com/Parclytaxel/f80ea90b8a7d15332feb673d209c885a">Python program</a>
%e n . minimal expression . number of 1's
%e 1...1....................1
%e 2...1+1..................2
%e 3...11...................2
%e 4...11+1.................3
%e 5...11+1+1...............4
%e 6...11*(1+1).............4
%e 7...111..................3
%e 8...111+1................4
%e 9...11*11................4
%e 10..11*11+1..............5
%e 11..11*11+1+1............6
%e 12..11*(11+1)............5
%e 13..11*(11+1)+1..........6
%e 14..111*(1+1)............5
%e 15..1111.................4
%e 16..1111+1...............5
%e 17..1111+1+1.............6
%e 18..11*11*(1+1)..........6
%e 19..11*11*(1+1)+1........7
%e 20..(11+1+1)(11+1).......7
%e 21..111*11...............5
%p with(numtheory):
%p a:= proc(n) option remember; (k-> `if`(2^k=n+1, k,
%p min(seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
%p seq(a(i)+a(n-i), i=1..n/2))))(ilog2(n+1))
%p end:
%p seq(a(n), n=1..120); # _Alois P. Heinz_, Jun 09 2016
%t 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]];
%t Array[a, 100] (* _Jean-François Alcover_, Mar 27 2017, after _Alois P. Heinz_ *)
%Y Cf. A005245, A133344.
%K nonn
%O 1,2
%A _Jeremy Tan_, Jun 08 2016
|
