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,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

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

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((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 *)

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).

Sequence in context: A070940 A020651 A294442 * A287051 A368147 A002487

Adjacent sequences: A281389 A281390 A281391 * A281393 A281394 A281395

Keyword

nonn

Author

Jeffrey Shallit, Jan 21 2017

Status

approved