nt.number-theory
Define the following two subsets of prime numbers
$$\Pi_n:=\{p: \text{$p$ is prime, $p\leq n$}\}$$
and
$$B_n:=\{p: \text{$p$ is prime, $p$ divides $\binom{n}k$ for some $0< k< n$}\}.$$
Denote their respective cardinalities by $\pi(n):=\vert\Pi_n\vert$ and $\,b(n):=\vert B_n\vert$.
QUESTIONS. Experimental evidence suggest that
(a) $\pi(n)-b(n)=0$ or $1$.
(b) If $\pi(n)-b(n)=1$, then the missing prime is the largest prime divisor of $n+1$.
Are these true statements?
It seems unlikely that one can prove anything nontrivial, but it's still interesting to consider what ought to be true, and to experimentally compute for small $k$.
Let
$$ \delta_k = \min_{\ell_1<\ell_2} \left(\frac{n_{\ell_2}}{n_{\ell_1}} - 1\right) = \min_{\ell} \left(\frac{n_{\ell+1}}{n_\ell} - 1\right), $$ so we're asking how small $\delta_k$ can get. An easy upper bound is $\delta_k \ll k \log k \, / \, 2^k$, and one can probably save some power of $k$. The right answer is probably $\delta_k \sim C^{-k + o(k)}$ for some constant $C>2$, and it seems reasonable to guess that $C=3$. I'll explain this next, followed by computational techniques that make it feasible to determine $\delta_k$ at least for $k \leq 36$; for example $$ \delta_{28} = \delta_{29} = \delta_{30} = \frac1{1079415718589} \doteq 3^{-25.22} $$ (the numerator is $13 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot 73 \cdot 89 = 2 \cdot 3 \cdot 5 \cdot 11 \cdot 17 \cdot 19 \cdot 31 \cdot 43 \cdot 71 \cdot 107 - 1$), and $$ \delta_{36} = \frac{145948}{123657879146878688901} \doteq 3^{-31.29} $$ with $$ 1 + \delta_{36} = \frac {7 \cdot 13 \cdot 19 \cdot 37 \cdot 41 \cdot 47 \cdot 73 \cdot 83 \cdot 89 \cdot 97 \cdot 127 \cdot 151} {3 \cdot 17 \cdot 23 \cdot 43 \cdot 59 \cdot 61 \cdot 67 \cdot 71 \cdot 79 \cdot 101 \cdot 131 \cdot 137}. $$
For the upper bounds: Note that $\delta_k$ is essentially $\min_{\ell_1<\ell_2} (\log n_{\ell_2} - \log n_{\ell_1}).$ There are $2^k$ numbers $\log n_\ell$ between $\log n_1 = 0$ and $\log n_{2^k} = \sum_{i=1}^k \log p_i \sim k \log k$; so when we list them in order the average difference is $\log n_{2^k} \, / \, (2^k - 1) \sim k \log k \, / \, 2^k$, and so there must be some difference(s) no larger than that. To save a power of $k$, note that the variance of the $2^k$ numbers $\log n_\ell$ is $\frac14 \sum_{i=1}^k \log^2 p_i \sim (k/4) \log^2 k$, and a positive fraction of them must be within say two standard deviations of the mean, so we get an upper bound $\sim k^{1/2} \log k \, /\, 2^k$.
For the heuristics: If we had $2^k$ random numbers in an interval, we'd expect the closest pair to be about $4^{-k}$ apart. But the separations aren't independent; there are only $(3^k-1)/2$ different ratios $n_{\ell_2} / n_{\ell_1}$ (namely the values of $\prod_{i=1}^k p_i^{\alpha_i}$ with each $\alpha_i \in \{-1, 0, 1\}$ that make the product $>1$), so we expect the smallest one to have logarithm about $3^{-k}$, again up to subexponential factors.
For small $k$ we can compute $\delta_k$ exactly by listing the $2^k$ factors of $\prod_{i=1}^k p_k$, sorting them, setting $\delta=2$, comparing each $n_{\ell+1} / n_\ell$ with the current value of $\delta$, and if $n_{\ell+1} / n_\ell$ is smaller then making it the new $\delta$. This takes about $2^k$ space and $k 2^k$ time.
We can reduce each factor $2^k$ to $3^{k/2}$ by splitting $\{p_1,\ldots,p_k\}$ into two equal or nearly equal subsets $P_1,P_2$, listing for $j=1,2$ all the $3^{P_j}$ rationals of the form $\prod_{p \in P_j} p^{\alpha_p}$ with each $\alpha_p \in \{-1, 0, 1\}$, merging and sorting the two lists, and minimizing over ratios between consecutive elements of different lists. This increases the feasible range by a factor of $\log_3 4 = 1.26\!+$, and is how I computed $\delta_k$ for $k \leq 36$ (in a few hours running gp on a computer on which I could allocatemem(2^37)). We next tabulate, for each $k \leq 36$, the values of $\log_3 (1 / \delta_k)$ (which does seem reasonably close to $k$), followed by the difference between the two $n_\ell$ with the ratio closest to $1$ and the values of those two $n_\ell$. When $\delta_k = \delta_{k-1}$ we use " marks instead of repeating a row.
1 | 0 1 2 1
2 | 0.631 1 3 2
3 | 1.465 1 6 5
4 | 2.402 1 15 14
5 | 2.771 1 22 21
6 | 3.954 1 78 77
7 | 5.981 1 715 714
8 | " " " "
9 | " " " "
10 | 7.030 1 2262 2261
11 | 8.559 1 12122 12121
12 | " " " "
13 | 10.491 1 101270 101269
14 | 10.765 7 958341 958334
15 | 13.277 1 2162095 2162094
16 | 13.385 9 21894574 21894565
17 | " " " "
18 | 14.237 269 1669770410 1669770141
19 | 15.039 296 4432525097 4432524801
20 | 16.459 95 6768250181 6768250086
21 | 17.492 1 221669903 221669902
22 | 17.989 479 183357752669 183357752190
23 | 20.727 1 7746395147 7746395146
24 | 20.899 241 2256564888159 2256564887918
25 | 22.260 31 1293752274846 1293752274815
26 | 22.260 31 1293752274846 1293752274815
27 | 23.709 8 1641739926263 1641739926255
28 | 25.220 1 1079415718590 1079415718589
29 | " " " "
30 | " " " "
31 | 28.015 3749 87225268563485259 87225268563481510
32 | 29.352 699715 70660131241710008586 70660131241709308871
33 | 30.221 208586 54759581443774708307 54759581443774499721
34 | " " " "
35 | 31.240 4 3216928369004441 3216928369004437
36 | 31.288 145948 123657879146878834849 123657879146878688901
This seems to agree with the computations of Gerhard Paseman up to $k=20$ (except for the error already noted in the final line). I couldn't find a sequence in OEIS that matches any of it.
One could push this computation further using the data structure described in this paper by D. J. Bernstein, which reduces the space requirement from $3^{k/2}$ (or $2^k$) to the square root $3^{k/4}$ (or $2^{k/2}$) without appreciably increasing the running time. I haven't tried to implement this.
Finally, for yet larger $k$ one could probably still exhibit some values of $n_{\ell+1} / n_{\ell}$ that are reasonably close to $1$ using algorithms such as LLL to find approximate integer relations on $\{ \log p_i \mid 1 \leq i \leq k \}$ (though it would be harder to prove that one has found the minimal one). I have not tried to do this either.
When $k$ is odd, writing $f_k(n)={n\choose k}+1$ you have $f_k(-1)=0$ as a polynomial evaluation, and removing the denominator gives you the extra $k!$ in integers.
I.e., $5!f_5(n)=n(n-1)(n-2)(n-3)(n-4)+120$, so $$5!f_5(-1)=(-1)(-2)(-3)(-4)(-5)+120=-120+120=0.$$ As $-1$ is a root of $f_k(n)$, then $n+1$ divides it (again consider denominators in the application).
Note also that all members of the "small sets" have $n+1$ dividing $k!$, showing that such sets are finite.
Best Answer
Suppose that $p $ is a prime satisfying $p\le n$ and $p\nmid \binom{n}{k}$ for all $k=1,\ldots,n-1.$ Then from Kummer's theorem it follows that the base-$p$ representation of $n$ is $n=(a,p-1,\ldots,p-1)_p$ with $1\le a\le p-1$. So $n=(a+1)p^r-1$, where $r$ is the number of base-$p$ digits in $n$. Then $n+1 = (a+1)p^r$ with $a+1 \leq p$, so any prime factor of $n+1$ besides $p$ is a prime factor of $a+1$, so it has to be less than $p$.
Here is a second solution, using Lucas's theorem: writing $n = n_0+n_1p+\cdots +n_rp^r$, where $0 \leq n_i \leq p-1$ and $n_r \geq 1$, each $k$ in $\{0,1,\ldots,n\}$ has base-$p$ representation $k_0+k_1p+\cdots +k_rp^r$ where $0 \leq k_i \leq p-1$ (maybe $k_r = 0$ if $k$ is much smaller than $n$). Then Lucas' theorem says $$ \binom{n}{k} \equiv \binom{n_0}{k_0}\binom{n_1}{k_1}\cdots \binom{n_r}{k_r} \bmod p. $$ For digits $n_i$ and $k_i$, which are in $\{0,1,\ldots,p-1\}$, we have $\binom{n_i}{k_i} \equiv 0 \bmod p$ if and only if $n_i < k_i$ (otherwise the factors in $\binom{n_i}{k_i} = \frac{n_i(n_i-1)\cdots(n_i-(k_i-1))}{k_i!}$ are all nonzero modulo $p$). Thus we have $\binom{n}{k} \not\equiv 0 \bmod p$ for all $k$ from $0$ to $n$ (let's allow $k=0$ and $k=n$ since those cases are not divisible by $p$) if and only if every $k \leq n$ has $k_i \leq n_i$ for $i < r$ and $k_r \leq n_r$, and that's equivalent to $n_i = p-1$ for $i < r$ (if some $n_i < p-1$ then at $k = (p-1)p^i$ we have $\binom{n}{k} \equiv 0 \bmod p$). Such $n$ have the form $(p-1)+(p-1)p\cdots+(p-1)p^{r-1} + n_rp^r = (n_r+1)p^r-1$. If $r = 0$ then $n = n_r \leq p-1$. If $r \geq 1$ then $p \mid (n+1)$, and the first solution shows easily in this case why $p$ has to be the largest prime factor of $n+1$. In summary, every prime that is $\leq n$ divides some $\binom{n}{k}$ for $1 \leq k \leq n-1$ except when $n = mp^r-1$ where $r \geq 1$, $p$ is prime, and $2 \leq m \leq p$, in which case the prime $p$ divides no $\binom{n}{k}$.