cp's OEIS Frontend

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

%I A281392 #12 Sep 19 2022 06:17:28
%S A281392 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 A281392 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 A281392 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 A281392 Number of occurrences of "01" as a subsequence in the binary expansion of n.
%C A281392 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 A281392 Robert Israel, <a href="/A281392/b281392.txt">Table of n, a(n) for n = 0..10000</a>
%F A281392 Completely defined by the recurrence relations
%F A281392 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 A281392 a(16n+13) = -a(n) + a(2n+1) + a(8n+5) with a(0) = 0, a(1) = 1 and a(5) = 3.
%e A281392 For n = 5, the number of occurrences of 01 as a subsequence of 0101 is 3.
%p A281392 f:= proc(n) option remember;
%p A281392   if n::even then procname(n/2)
%p A281392   elif n mod 4 = 3 then - procname((n-3)/4) + 2*procname((n-1)/2)
%p A281392 elif n mod 8 = 1 then -procname((n+3)/4) + 2*procname((n+1)/2)
%p A281392 elif n mod 16 = 5 then -2*procname((n+3)/8) + 2*procname((n-1)/4) + procname((n+5)/2)
%p A281392 elif n mod 16 = 13 then -procname((n-13)/16) +procname((n-5)/8) + procname((n-3)/2)
%p A281392 fi;
%p A281392 end proc:
%p A281392 f(0):= 0: f(1):= 1: f(5):= 3:
%p A281392 map(f, [$0..200]); # _Robert Israel_, Mar 11 2020
%t A281392 f[n_] := f[n] = Which[
%t A281392 EvenQ[n], f[n/2],
%t A281392 Mod[n, 4] == 3, -f[(n-3)/4] + 2*f[(n-1)/2],
%t A281392 Mod[n, 8] == 1, -f[(n+3)/4] + 2*f[(n+1)/2],
%t A281392 Mod[n, 16] == 5, -2*f[(n+3)/8] + 2*f[(n-1)/4] + f[(n+5)/2],
%t A281392 Mod[n, 16] == 13, -f[(n-13)/16] + f[(n-5)/8] + f[(n-3)/2]];
%t A281392 f[0] = 0; f[1] = 1; f[5] = 3;
%t A281392 Map[f, Range[0, 200]] (* _Jean-François Alcover_, Sep 19 2022, after _Robert Israel_ *)
%Y A281392 Cf. A055941, which gives the analogous sequence for the pattern "10" instead of "01".
%Y A281392 Cf. A000079 (a(n)=1), A007283 (a(n)=2), A070875 (a(n)=3).
%K A281392 nonn
%O A281392 0,4
%A A281392 _Jeffrey Shallit_, Jan 21 2017