Minimum Number of Values to Guess a Polynomial with Non-Negative Coefficients My math teacher claimed that he could guess any polynomial with non-negative coefficients given two values that he asked for. For example, he asked me to write down a function of which I wrote down (x^5 + 3x^2) and didn't tell him. Simply by knowing the values of f(1) and f(5), he was able to guess the function with accuracy. Is this pure guessing or is there a mathematical explanation for it? Need to know a minimum of two values to guess a polynomial with non-negative coefficients. 
 A: Just for the record, I thing it may be described this way: being told $f(1) = A,$ ask for $f(1+A) = B$ and then write $B$ in base $(A+1).$
So, $$ 3200_{\mbox{base ten}}  \equiv 100300_{\mbox{base five}}   $$
A: Yes, it is possible to guess the polynomial with only two queries. The trick here is that the second query depends on the first (otherwise, if all queries are independent, then by polynomial interpolation, we'd need at least as many queries as one plus the degree of the polynomial). The algorithm is as follows:


*

*Ask for $f(1)$, and call it $A$.

*Ask for $f(A + 1)$, and call it $B$.

*Initialize $i := 0$.

*While $B \neq 0$, do the following:

*

*Set $c_i := B \pmod {A+1}$.

*Set $B := \frac{B - c_i}{A+1}$.

*Increment $i := i + 1$.




For your example, we have:


*

*$A = f(1) = 4$

*$B = f(A + 1) = f(5) = 3200$

*

*$c_0 = 3200 \pmod 5 = 0$

*$c_1 = \frac{3200 - 0}{5} \pmod 5 = 640 \pmod 5 = 0$

*$c_2 = \frac{640 - 0}{5} \pmod 5 = 128 \pmod 5 = 3$

*$c_3 = \frac{128 - 3}{5} \pmod 5 = 25 \pmod 5 = 0$

*$c_4 = \frac{25 - 0}{5} \pmod 5 = 5 \pmod 5 = 0$

*$c_5 = \frac{5 - 0}{5} \pmod 5 = 1 \pmod 5 = 1$



Putting it together, we obtain $f(x) = \sum_{i=0}^5c_ix^i = 3x^2 + x^5$, as desired.

The reasoning here is that:
$$
B = c_0 + c_1(A + 1) + c_2(A + 1)^2 + \cdots + c_d(A + 1)^d
$$
So modding out by $A + 1$ will make all of the powers of $A + 1$ vanish and leave behind the smallest coefficient. Modding $c_0$ by $A + 1$ won't affect the coefficient, since all coefficients are nonnegative and $A$ is the sum of all coefficients, so each coefficient is guaranteed to be in the range $[0, A]$.
A: Here is a fascinating way of finding the polynomial with two questions!
Ask for $f(1)$. Say it's around $500$.
Ask for $f(0.001)$ (Add an appropriate number of zeroes after the decimal point depending on how large $f(1)$ is).
The coefficients will all separate in the decimal expansion.
Example : $f(x)=x^5 + 3x^2$
$f(1) = 4$
Ask for $f(0.1) = 0.03001$
It seems foolproof (of course, provided that coefficients are non-negative integers.)
