Puzzle time - Recovering the Polynomial

[jon-nyc]

The Oracle at Delphi has in mind a certain polynomial p (in the variable x, say) with non-negative integer coefficients. You may query the Oracle with any integer n, and the Oracle will tell you the value of p(n).

How many queries do you have to make to determine p?

[Horace]

Well n+1 points define a polynomial of order n, in the same way that two points define a line, but the restriction to non-negative integer coefficients must make a better answer possible. The way the question is worded implies that a constant answer suffices for polynomials of any order. Can a polynomial expression with non-negative integer coefficients be simplified into a form of a(x^n)+b?

But the answer is probably not to simplify it a priori, but rather to gather information from the first guess to narrow down which would be the most informative next guess.

[Klaus]

I'd start with p(1).

If p(1) = m , then all coefficients must be <= m.

That reduces the number of candidates quite a bit.

[Klaus]

Ah, I think I got it!

click to show

Assume all coefficients were <= 9.

Then a Oracle single invocation would suffice, namely p(10). The digits of the results would be the coefficients because p(10) = d-n 10^n + ... + d-0 10^0 = d-n...d-0.

But we can apply the same trick when we only know an upper bound m on the coefficient; we simply take p(m+1) and interpret the result as a number in base m+1. Again, the digits of the result will be the coefficients.

I already explained above how to get the upper bound with one invocation. In total, it takes just two invocations of the oracle!

[Horace]

@Klaus said in Puzzle time - Recovering the Polynomial:

Ah, I think I got it!

click to show

Assume all coefficients were <= 9.

Then a Oracle single invocation would suffice, namely p(10). The digits of the results would be the coefficients because p(10) = d-n 10^n + ... + d-0 10^0 = d-n...d-0.

But we can apply the same trick when we only know an upper bound m on the coefficient; we simply take p(m+1) and interpret the result as a number in base m+1. Again, the digits of the result will be the coefficients.

I already explained above how to get the upper bound with one invocation. In total, it takes just two invocations of the oracle!

click to show

Oh, yeah, boils down to a way of thinking in number bases. Nice.

[jon-nyc]

Very nice Klaus and a very surprising result given it works for any n.

[Klaus]

I think if I could query the oracle with any number, not just integers, I could do it with just one query.

Just take an arbitrary transcendental number (such as Pi). No two integer-coefficient-polynomials will agree on that number. Enumerate all non-negative-coefficient-polynomials until you get to the one that agrees with the result. (the method is not entirely practical, though, because it depends on comparing numbers that cannot be finitely represented with digits).