14
$\begingroup$

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?

$\endgroup$
22
$\begingroup$

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}

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

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]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.