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?


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<98$ then $P^{\star}(x)$, despite of being of degree $d+1$, would have $>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>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)$.
