Does This Polynomial Even Exist?

Firstly I would like to point out that there is a mistake in the problem. It should be $2<n\le100$ rather than the other way round. The answer would be 35 if it meant this exactly.

The problem will be split into two parts: - The case when $n$ has two or more distinct prime factors. - The case when $n$ can be written as $p^a$ where $p$ is prime and $a$ is a positive integer larger than 1.

Now for the first case we shall show that there cannot exist a polynomial for $n$ . Assume there is such a polynomial for $n$ . Let $n=p_1^{\delta_1}p_2^{\delta_2}\cdots p_k^{\delta_k}$ . Now let $f(x)$ have denominator $q>1$ . Now using Newtonian interpolation which is defined for a polynomial of degree $<n$ $f(\omega+n) =\sum_{i = 0}^{n-1}(-1)^{n-1-i}\binom{n}{i}f(\omega+i)$ For some $1\le s\le k$ we therefore have $f(p_s^{\delta_s}+n) =\sum_{i = 0}^{n-1}(-1)^{n-1-i}\binom{n}{i}f(p_s^{\delta_s}+i)$ . Now note that the LHS is an integer. All terms on the right hand side are also integers maybe except for $\binom n{n-p^{\delta_s}_s}f(n)$ term. However this must mean that it is an integer. Now noting that $p_s\nmid \binom{n}{p^{\delta_s}_s}\implies p_s \nmid q$ . This holds for any $s$ (within limits) therefore we have $\gcd(n, q)=1$ . Finally take $\omega=1$ for the interpolation formula and we recieve $f(1+n) =\sum_{i = 0}^{n-1}(-1)^{n-1-i}\binom{n}{i}f(1+i)$ . Once again, on the LHS and RHS, all terms are integers except possible for $\binom n1 f(n)$ term. However this also must be an integer. So we can say that $q\nmid n$ . But $\gcd(q, n)=1\implies q=1$ thus a contradiction. Therefore $n$ cannot have two or more distinct prime factors.

Finally, for any $n=p^a$ we have a polynomial that satisfies the condition, namely $f(x) =\frac{p^{a-1}(x-1)(x-2)\ldots(x-p^a+1)}{(p^a)!}$ . This can easily be checked to show that it satisfies the conditions.

Counting all prime powers between $2$ and $100$ we get $\cancel{\boxed{34}}$ . (See edit below)

Note : I do believe that this problem is one of the best on brilliant.org. Trying to solve it has opened my mind up to new skills and techniques and inspired me to learn more! The total time I spend on this problem is around 15 hours. But hey exams are over!

---

EDIT Now that the question's answer has been modified to suit the original wording we can ignore my note at the top. As $2$ is prime, we add one to our count which gives us $\boxed{35}$ .