This is related to a question in The Math Connection on LinkedIn and following discussion. It goes as follows:
There is a polynomial and you have access to a function that evaluates that polynomial at a given number. You don’t know the degree of the polynomial, nor do you know any of the coefficients of its terms. However, you are told that all coefficients are non-negative integers. How many times do you need to call the evaluation function in order to identify the polynomial (that is, to figure out the values of its coefficients)?
Spoilers ahead, think about the question first if you wish
The conclusion was twice. Evaluation one is $P(1)$, where your unknown polynomial is $P$. If $P(1) = 0$, then it is easy, $P = 0$. Otherwise, evaluate $P(P(1) + 1)$ and express it in the base $P(1) +1$. The coefficients of $P$ are the coefficients of the base $P(1) + 1$ representation of $P(P(1) + 1)$.
As an example, given the original question constraints on a function $f$ and the following information, find $f$: $$f(1)=204$$ $$f(205)=1087670038021112932720656963356516921366795452188514173030853271504472$$
Spoilers again - if you wish to think first
$f(x)$ was found to be $99*x^{29} + 98*x + 7$
Thus, my real question arises, how would we figure out what $f$ is in the above example? I've milled over it, and I can't think of any way to do it other than using a computer program. Is there any nice way to find $f$ without use of a computer? If we do have to use a computer how might the code look?
Many thanks for any discussion or help.
Thinking about that answer...
If $m$ is any integer greater than any of the coefficients, then, if $f(x) =\sum_{k=0}^d a_kx^k $, $f(m) =\sum_{k=0}^d a_km^k $.
If we write $f(m)$ in base $m$, then this will be the same as $\sum_{k=0}^d a_km^k$ since all the $m$-digits will be small enough to not carry.
This reduces the problem to finding an $m$ which is greater than any of the coefficients, and choosing $m = f(1)+1 =1+\sum_{k=0}^d a_k $ does this since each $a_k \ge 0$.