Finding the number of multiple of $3$ in the coefficients of $x(x+1)(x+2)\cdots (x+239)$

Question

Suppose $$ x(x+1)(x+2)\cdots(x+239)=\sum_{n=1}^{240}a_nx^n $$ What's the total number of $a_n$ which is exactly the multiple of $3$?

I've calculated using Mathematica and got the answer is $160$, but I don't know how to solve it using Number Theory. This is my Mathematica code:

Tr[Divisible[CoefficientList[Product[(x + i), {i, 1, 240}], x][[2 ;; 240]], 3]]

and get

80 False + 159 True

Answer 1

Hint. We have that $$\prod_{n=0}^{239}(x+n)\equiv \left(x(x+1)(x-1)\right)^{80}= x^{80}(x^2-1)^{80}=x^{80}\sum_{k=0}^{80}\binom{80}{k}(-x^{2})^k\pmod{3}.$$ So your answer is correct as soon as you show that $\binom{80}{k}$ is not a multiple of $3$ for all $k=0,1,\dots,80$. Note that $80=3^4-1=2\cdot 3^3+2\cdot 3^2+2\cdot 3^1+2\cdot 3^0$ and use Lucas's theorem.

Answer 2

Some variant based on Robert Z's answer not requiring evaluating $\binom{80}{k}\pmod 3$, even though it is the same at final.

Note that $(x-1)^2(x+1)^2=(x^2-1)^2=x^4-2x^2+1\equiv 1+x^2+x^4\pmod 3$

Then we also have a pattern for the cube of such expressions:

• $(1+x^2+x^4)^3\equiv 1+x^6+x^{12}\pmod 3$
• $(1+x^6+x^{12})^3\equiv 1+x^{18}+x^{36}\pmod 3$
• $(1+x^{18}+x^{36})^3\equiv 1+x^{54}+x^{108}\pmod 3$

Since $80=2+6+18+54$

The product is in fact $$\quad x^{80}(1+x^2+x^4)(1+x^6+x^{12})(1+x^{18}+x^{36})(1+x^{54}+x^{108})\pmod 3$$

And we can see it develops to $\displaystyle \sum\limits_{k=40}^{120} x^{2k}$ because all powers are different.

There are $120-40+1=81$ terms.