2019 AMC 12A Problem 24

Fix a prime $p\le n.$ By Legendre’s formula, the difference between the exponent of $p$ in the numerator and its exponent in the denominator is $$\begin{aligned} D_p &=\sum_{k\ge1}\left\lfloor\dfrac{n^2-1}{p^k}\right\rfloor\\ &\quad-n\sum_{k\ge1}\left\lfloor\dfrac{n}{p^k}\right\rfloor. \end{aligned}$$ If $r_k$ is the remainder of $n$ modulo $p^k,$ the $k$th summand is $\left\lfloor\dfrac{nr_k-1}{p^k}\right\rfloor.$ Let $a=v_p(n).$ The first $a$ summands are $-1.$ If $n$ is not a power of $p,$ write $n=p^a m$ with $m\ge2.$ When $a\ge1,$ the next summand is at least $\dfrac{n}{p}-1\ge a,$ and all later summands are nonnegative; when $a=0,$ every summand is already nonnegative. Thus $D_p\ge0$ unless $n$ is a power of $p.$ For $n=p^a,$ Legendre’s formula reduces the requirement to $p^a-1\ge2a(p-1).$ Among prime powers at most $50,$ this fails exactly when $a=1$ (so $n$ is prime) and when $n=2^2=4.$ There are $15$ primes at most $50,$ plus $n=4,$ giving $16$ failures. Hence $50 - 16 = 34$ values of $n$ work. Thus, the correct answer is D.