n choose k is NOT divisible by some prime number p if and only if:
\(\{\frac{k}{p^i}\} \leq \{\frac{n}{p^i}\} \) ({x} is the fractional part of x) for all \(i\in\mathbb{N}\)
In other words, if the representation of n in base p is amam-1....a0 and the representation of k in base p is bmbm-1....b0 then n choose k is NOT divisible by p if and only if \(\forall 0\leq i \leq m\enspace b_i \leq a_i\)
conclusion: if the representation in base p of n is amam-1....a0 then there are exactly \(\prod_{i=0}^{m} (a_i+1)\) values of k between 0 and n such that n choose k is NOT divisible by p
EDIT: here's a useful stack exchange thread