Binomial coefficient: Search for multiples of 13

Question

Question: The coefficients of how many terms in the expansion of (1+x)²⁰¹⁸ are multiples of 13?

So, we've to investigate the powers of 13 in ${2018 \choose r}$, where 0 ≤ r ≤ 2018

I tried using the following: $$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

where, $s_p(N!)$ denotes the highest exponent of prime p in n!, where n is a natural number.

${2018 \choose r}$, may be written as $\frac{2018!}{r!(2018-r)!}$. Now, I tried to figure out the exponent of 13 in numerator for several values of r, but couldn't find a pattern that would lead me to the desired answer.

Could someone please give a detailed solution to this problem, and also explain how to approach such problems? Is there any generalisation for the multiples of a prime number p in ${n \choose r}$?

P.S. The answer, to the best of my recollection, is 1395.

Answer 1

Hint:

$$E_{13}(2018!)=\left \lfloor \frac {2018}{13}\right \rfloor+\left \lfloor \frac {2018}{13^2}\right \rfloor+\left \lfloor \frac {2018}{13^3}\right \rfloor \ldots $$ $$=155+11+0$$ $$=166$$

$$\Rightarrow E_{13}(r!) +E_{13}((2018-r)!)\le 165$$ $$\Rightarrow r=13\lambda +k, k=4,5,6,7,8,9,10,11,12$$

For $r=13\lambda+ 4$ we have following $155$ numbers $$r=4,17,30,....., 2006$$

And continue similarly for other values of $k$

$$\Rightarrow Total = 155*9=1395$$

Answer 2

According to Kummer's Theorem, as shown in this answer,

The number of factors of $p$ in $\binom{n}{k}$ is the number of carries in the addition $k+(n-k)=n$ when performed in base-$p$.

This means that the binomial coefficients $\binom{2018}{k}$ that are not divisible by $13$ are those where $k+(BC3_{13}-k)=BC3_{13}$ has no carries. That would be those with digits $0$-$B$ in the $13^2$ digit, $0$-$C$ in the $13^1$ digit, and $0$-$3$ in the $13^0$ digit. That is, there are $12\cdot13\cdot4=624$ coefficients which do not have a factor of $13$.

Thus, there are $2019-12\cdot13\cdot4=1395$ coefficients that have a factor of $13$.