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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 21 2017
STATUS
approved