

A281392


Number of occurrences of "01" as a subsequence in the binary expansion of n.


1



0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 4, 3, 4, 1, 5, 4, 7, 3, 6, 5, 7, 2, 5, 4, 6, 3, 5, 4, 5, 1, 6, 5, 9, 4, 8, 7, 10, 3, 7, 6, 9, 5, 8, 7, 9, 2, 6, 5, 8, 4, 7, 6, 8, 3, 6, 5, 7, 4, 6, 5, 6, 1, 7, 6, 11, 5, 10, 9, 13, 4, 9, 8, 12, 7, 11, 10, 13, 3, 8, 7, 11, 6, 10, 9, 12, 5, 9, 8, 11, 7, 10, 9, 11, 2, 7, 6, 10, 5, 9, 8, 11, 4, 8, 7, 10, 6, 9, 8, 10, 3, 7, 6, 9, 5, 8, 7, 9, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

By "subsequence" we do not demand that occurrences are contiguous. Furthermore, we assume that the binary expansion of n begins with a 0, and is read starting with the most significant digit.


LINKS



FORMULA

Completely defined by the recurrence relations
a(2n) = a(n); a(4n+3) = a(n) + 2a(2n+1); a(8n+1) = a(2n+1) + 2a(4n+1); a(16n+5) = 2a(2n+1) + 2a(4n+1) + a(8n+5);
a(16n+13) = a(n) + a(2n+1) + a(8n+5) with a(0) = 0, a(1) = 1 and a(5) = 3.


EXAMPLE

For n = 5, the number of occurrences of 01 as a subsequence of 0101 is 3.


MAPLE

f:= proc(n) option remember;
if n::even then procname(n/2)
elif n mod 4 = 3 then  procname((n3)/4) + 2*procname((n1)/2)
elif n mod 8 = 1 then procname((n+3)/4) + 2*procname((n+1)/2)
elif n mod 16 = 5 then 2*procname((n+3)/8) + 2*procname((n1)/4) + procname((n+5)/2)
elif n mod 16 = 13 then procname((n13)/16) +procname((n5)/8) + procname((n3)/2)
fi;
end proc:
f(0):= 0: f(1):= 1: f(5):= 3:


MATHEMATICA

f[n_] := f[n] = Which[
EvenQ[n], f[n/2],
Mod[n, 4] == 3, f[(n3)/4] + 2*f[(n1)/2],
Mod[n, 8] == 1, f[(n+3)/4] + 2*f[(n+1)/2],
Mod[n, 16] == 5, 2*f[(n+3)/8] + 2*f[(n1)/4] + f[(n+5)/2],
Mod[n, 16] == 13, f[(n13)/16] + f[(n5)/8] + f[(n3)/2]];
f[0] = 0; f[1] = 1; f[5] = 3;


CROSSREFS

Cf. A055941, which gives the analogous sequence for the pattern "10" instead of "01".


KEYWORD

nonn


AUTHOR



STATUS

approved



