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

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

Offset: 0

Author

Jeffrey Shallit, Jan 21 2017

Keywords

• nonn

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.

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 0..10000

Crossrefs

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

Cf. A000079 (a(n)=1), A007283 (a(n)=2), A070875 (a(n)=3).

Programs

Maple

f:= proc(n) option remember;
  if n::even then procname(n/2)
  elif n mod 4 = 3 then - procname((n-3)/4) + 2*procname((n-1)/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((n-1)/4) + procname((n+5)/2)
elif n mod 16 = 13 then -procname((n-13)/16) +procname((n-5)/8) + procname((n-3)/2)
fi;
end proc:
f(0):= 0: f(1):= 1: f(5):= 3:
map(f, [$0..200]); # Robert Israel, Mar 11 2020

Mathematica

f[n_] := f[n] = Which[
EvenQ[n], f[n/2],
Mod[n, 4] == 3, -f[(n-3)/4] + 2*f[(n-1)/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[(n-1)/4] + f[(n+5)/2],
Mod[n, 16] == 13, -f[(n-13)/16] + f[(n-5)/8] + f[(n-3)/2]];
f[0] = 0; f[1] = 1; f[5] = 3;
Map[f, Range[0, 200]] (* Jean-François Alcover, Sep 19 2022, after Robert Israel *)

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.