A281392 - OEIS

%I #12 Sep 19 2022 06:17:28

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

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

%U 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

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

%C 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.

%H Robert Israel, <a href="/A281392/b281392.txt">Table of n, a(n) for n = 0..10000</a>

%F Completely defined by the recurrence relations

%F 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);

%F a(16n+13) = -a(n) + a(2n+1) + a(8n+5) with a(0) = 0, a(1) = 1 and a(5) = 3.

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

%p f:= proc(n) option remember;

%p   if n::even then procname(n/2)

%p   elif n mod 4 = 3 then - procname((n-3)/4) + 2*procname((n-1)/2)

%p elif n mod 8 = 1 then -procname((n+3)/4) + 2*procname((n+1)/2)

%p elif n mod 16 = 5 then -2*procname((n+3)/8) + 2*procname((n-1)/4) + procname((n+5)/2)

%p elif n mod 16 = 13 then -procname((n-13)/16) +procname((n-5)/8) + procname((n-3)/2)

%p fi;

%p end proc:

%p f(0):= 0: f(1):= 1: f(5):= 3:

%p map(f, [$0..200]); # _Robert Israel_, Mar 11 2020

%t f[n_] := f[n] = Which[

%t EvenQ[n], f[n/2],

%t Mod[n, 4] == 3, -f[(n-3)/4] + 2*f[(n-1)/2],

%t Mod[n, 8] == 1, -f[(n+3)/4] + 2*f[(n+1)/2],

%t Mod[n, 16] == 5, -2*f[(n+3)/8] + 2*f[(n-1)/4] + f[(n+5)/2],

%t Mod[n, 16] == 13, -f[(n-13)/16] + f[(n-5)/8] + f[(n-3)/2]];

%t f[0] = 0; f[1] = 1; f[5] = 3;

%t Map[f, Range[0, 200]] (* _Jean-François Alcover_, Sep 19 2022, after _Robert Israel_ *)

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

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

%K nonn

%O 0,4

%A _Jeffrey Shallit_, Jan 21 2017