Given a polynomial $P$ with integer coefficients, find $P(2)$

Question

Question:

$P(x)$ be a polynomial with non-negative integer coefficients such that $P(0)=33$ , $P(1)=40$ and $P(9)=60000$.

Find $P(2)$.

My attempt:

Suppose $P(x) = a_nx^n + \dotsb + a_1x + a_0$.

Now, $P(0) = 33$ implies $a_0 = 33$.

$P(1)=40$ implies that the sum of the coefficients other than constant term is $7$. Also, $$P(9)-P(0)=3(2^5\times5^4-11)=3^2a_{1}+3^4a_{2}+\dotsb+a_n3^{2n}.$$ Dividing both sides by $3^3$ we can easily infer $a_{1}=3$. After solving it further, I ended up with $$a_{2}+3a_{3}+\dotsb a_{n}3^{2n-3}=740,$$ but I can't find $P(2)$.

There are few more coefficients remaining other than $a_{1}$ whose sum is $4$, and I think casework can give a solution... like assuming consecutive $4$ coefficients $1$, $1$, $1$, $1$; $1$, $2$, $1$ etc., but I don't want to go that way.

Answer 1

As mentioned earlier, the sum of all coefficients is $40$, and the first coefficient is $33$. So the sum of the rest of the coefficients is $7$. All we can do is go modulo powers of $9$, since for each $n$ we have $\sum_{k=0}^n a_k9^k \equiv P(9) \mod 9^{n+1}$.

Of this, we go mod $81$ : $60000$ leaves remainder $60$ upon division by $81$. So, $9a_1 + 33$ leaves the same remainder upon division by $81$. This of course gives $a_1 = 3$ by uniqueness.

Next go mod $729$ : $60000$ leaves remainder $222$, so $81a_2 + 60 = 222$ by uniqueness, giving $a_2 = 2$.

Go mod $6561$ : $60000$ leaves remainder $951$, so $222 + 729a_3 = 951$ giving $a_3 = 1$.

Finally $59049$, gives the same remainder , so $a_4 = 0$.

Go modulo $9^6 > 60000$ : this simply gives $a_5 = 1$, since the remainder is $60000$. No more coefficients can be non-zero : they add up to $40$ now.

So the polynomial is $x^5 + x^3 + 2x^2+3x+33$. One checks that the conditions are satisfied and all coefficients are non negative.

Finally the answer is when you substitute $2$ in here : $32+8+8+6+33 = 87$.

Answer 2

The polynomial can be at most of degree $4$ because

$9^5=59409$

so

$p(x)=33+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5$

and

$a_1+a_2+a_3+a_4+a_5=7$

It is clear that $a_5=1$ otherwise

if $a_5=0$ then $p(9)<60000$

while if $a_5>1$ then $a_59^5>60000$

If $a_4\neq 0$ then $p(9)>60000$ so $a_4=0$. If $a_3=0$ we have

$a_1+a_2=6$

$9a_1+81a_2=918$

that it has not solutions

So We must suppose $a_3\neq 0$ and We must compute

$a_1+a_2+a_3=6$

$9a_1+81a_2+729a_3=918$

This means $a_3=1$ and so

$a_1+a_2=5$

So is clear that We must have $a_1=3$ and $a_2=2$. So the polinomial is

$p(x)=33+3x+2x^2+x^3+x^5$