OFFSET
0,2
COMMENTS
This is the Run Length Transform of S(n) = Fibonacci(n+2).
The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g. 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product).
Also the number of sparse subsets of the binary indices of n, where a set is sparse iff 1 is not a first difference. The maximal case is A384883. For prime instead of binary indices we have A166469. - Gus Wiseman, Jul 05 2025
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..8191
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166 [math.CO], 2016.
FORMULA
a(n) = Sum_{k=0..n} ({binomial(3k,k)*binomial(n,k)} mod 2). - Chai Wah Wu, Oct 19 2016
EXAMPLE
From Gus Wiseman, Jul 05 2025: (Start)
The binary indices of 11 are {1,2,4}, with sparse subsets {{},{1},{2},{4},{1,4},{2,4}}, so a(11) = 6.
The maximal runs of binary indices of 11 are ((1,2),(4)), with lengths (2,1), so a(11) = F(2+2)*F(1+2) = 6.
The a(0) = 1 through a(12) = 3 sparse subsets are:
0 1 2 3 4 5 6 7 8 9 10 11 12
------------------------------------------------------------------
{} {} {} {} {} {} {} {} {} {} {} {} {}
{1} {2} {1} {3} {1} {2} {1} {4} {1} {2} {1} {3}
{2} {3} {3} {2} {4} {4} {2} {4}
{1,3} {3} {1,4} {2,4} {4}
{1,3} {1,4}
{2,4}
The greatest number whose set of binary indices is a member of column n above is A374356(n).
(End)
MAPLE
with(combinat); ans:=[];
for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;
for i from 1 to L1 do
if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;
elif out1 = 0 and t1[i] = 1 then c:=c+1;
elif out1 = 1 and t1[i] = 0 then c:=c;
elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;
fi;
if i = L1 and c>0 then lis:=[c, op(lis)]; fi;
od:
a:=mul(fibonacci(i+2), i in lis);
ans:=[op(ans), a];
od:
ans;
MATHEMATICA
a[n_] := Sum[Mod[Binomial[3k, k] Binomial[n, k], 2], {k, 0, n}];
a /@ Range[0, 100] (* Jean-François Alcover, Feb 29 2020, after Chai Wah Wu *)
spars[S_]:=Select[Subsets[S], FreeQ[Differences[#], 1]&];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[spars[bpe[n]]], {n, 0, 30}] (* Gus Wiseman, Jul 05 2025 *)
PROG
(PARI) a(n)=my(s=1, k); while(n, n>>=valuation(n, 2); k=valuation(n+1, 2); s*=fibonacci(k+2); n>>=k); s \\ Charles R Greathouse IV, Oct 21 2016
(Python)
# use RLT function from A278159
from sympy import fibonacci
def A245564(n): return RLT(n, lambda m: fibonacci(m+2)) # Chai Wah Wu, Feb 04 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Aug 10 2014; revised Sep 05 2014
STATUS
approved