For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n and k) using the Lucas theorem.
I am looking for a way to be able to count the the number of coefficients ( ${ n \choose k}$ k $\in$ [0,n] ) divisible by prime p without going through all of them at once and checking for each of the coefficients.Or can we count the coefficients not divisible by the prime p and subtract from n+1?
How do we approach this ?