Finding the number of odd quintinomial coefficients
Use PolynomialMod
:
Length @ PolynomialMod[(x^4+x^3+x^2+x+1)^12207, 2] //AbsoluteTiming
Length @ PolynomialMod[(x^4+x^3+x^2+x+1)^27637, 2] //AbsoluteTiming
{0.636855, 16333}
{2.20654, 31973}
Upon further reflection, even better would be to use Expand
:
Length @ Expand[(x^4+x^3+x^2+x+1)^12207, Modulus->2] //AbsoluteTiming
Length @ Expand[(x^4+x^3+x^2+x+1)^27637, Modulus->2] //AbsoluteTiming
{0.012514,16333}
{0.023518,31973}
A slower but still useful approach employs ListCorrelate
.
ct[n_] := Total@Nest[Mod[ListCorrelate[{1, 1, 1, 1, 1}, #, {-1, 1}, 0], 2] &,
{1, 1, 1, 1, 1}, n - 1]
ct[12207] // AbsoluteTiming
(* {6.49148, 16333} *)
ct[27637] // AbsoluteTiming
(* {31.4737, 31973} *)
The advantage of this approach is that, being recursive, it provides ct
for all intermediate values of n
at only modest additional cost.
t = Total /@ NestList[Mod[ListCorrelate[{1, 1, 1, 1, 1}, #, {-1, 1}, 0], 2] &,
{1, 1, 1, 1, 1}, 27636]; // AbsoluteTiming
(* {45.2923, Null} *)
ListPlot[t, PlotRange -> All]