cp's OEIS Frontend

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.

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