MIT PRIMES Question, polynomial satisfying conditions There was an MIT PRIMES application problem that goes like this: (don't worry, the admission ended on Dec 1, so I'm not cheating or anything)

For all $d\geq 0$, determine if there is a polynomial $p(x)$ with degree $d$ such that for all $n$ in $1\ldots 99$ inclusive satisfies $$p(n)=n+\frac1n$$ and if so, what is $p(x)$ and find the value of $p(100)$.

In English terms: find a polynomial with degree $d$ such that $$p(1)=1+\frac11=2$$ $$p(2)=2+\frac12=2.5$$ and so on. What values of $d$ work? What are the polynomials for each of those $d$? What is $p(100)$ for each of those polynomials?

My solution was to brute force it by solving a matrix (see Finding polynomials from huge sets of points), but Java wasn't good enough to do all that math (couldn't contain huge numbers with good enough precision).


  Is there a better, more elegant way to do the problem? If not, how would I brute force it?
If $p(x)$ satisfies the given conditions, then
$$ f(x) = xp(x)-x^2-1 $$
is a polynomial of degree $d+1$ (assuming $d\geq 1$) with zeros at $x = 1,2,\ldots,99$.

Note that $f$ satisfies $f(0) = -1$, so it cannot be the polynomial that is identically zero-valued. Thus $f$ can have at most $d+1$ distinct zeros,
so we must have $d\geq 98$.



If $d = 98$, then the location of zeros of $f(x)$ implies
$$f(x) = k(x-1)(x-2)\cdots(x-99)$$
for some constant $k$. 
But since
$$ -1 = f(0) = k\cdot(-1)^{99}(99!),$$
we may solve for $k = \frac1{99!}$. In this case $f(100) = k\cdot(99!) = 1$, so then
$$p(100) = \frac1{100} (f(100) + 100^2 + 1) = 100 + \frac2{100}.$$



If $d\geq 99$, then we have
$$f(x) = \frac1{99!}(x-1)(x-2)\cdots(x-99)g(x)$$
for some (arbitrary) polynomial $g(x)$ of degree $d - 98$, normalized to $g(0) = 1$.
In this case $f(100) = g(100)$, and 
$$ p(100) = \frac1{100} (g(100) + 100^2 + 1 ) = 100 + \frac{1 + g(100)}{100}.$$
From the given condition $nP(n)=n^2+1$ for $n=1,2,\cdots,99$. So the polynomial $P^{\star}(x)=xP(x)-x^2-1$ of degree $d+1$, has 99 zeros. If $d&lt;98$ then $P^{\star}(x)$, despite of being of degree $d+1$, would have $&gt;d+1$ roots, and hence should be identically equal to zero for every $x$. Then $P(100)$ would be simply $\frac{P^{\star}(100)+(100^2+1)}{100}=100+\frac1{100}$. 

Now if $d=98$ then we can represent 
$$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)$$
assuming $P$ to be a monic polynomial. Then $P(100)=\frac{P^{\star}(100)+(100^2+1)}{100}=\frac{99!+10001}{100}$.

If $d&gt;98$ then we can represent 
$$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)g(x)$$
With $g(x)$ being a polynomial of degree $\ge1$. But then due to indeterminacy of $g(x)$ we can't calculate the exact value of $P(100)$.