# Finding the number of odd quintinomial coefficients

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?

• With the help of some internal code: In[4]:= Timing[ Total[AlgebraPolynomialPowerModList[{1, 1, 1, 1, 1}, 27637, 2]]] Out[4]= {0.012, 31973} – Daniel Lichtblau Dec 15 '19 at 1:07

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}

• I'm really impressed! thank you very much – J42161217 Feb 13 '17 at 9:40

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]
`