Finding the number of odd quintinomial coefficients

Question

I am searching for the number of odd coefficients of

$\qquad (x^4 + x^3 + x^2 + x + 1)^n$

for arbitrary $n$.

It took some hours to compute the result for $n=12207$. There are $16333$ odd coefficients.

I need to compute it for $n=27637$ as well. I tried

Total[CoefficientList[(x^4 + x^3 + x^2 + x + 1)^27637, x, Modulus -> 2]]

but it is too slow.

Are there faster ways to do it?

Answer 1

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}

Answer 2

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]