Problem 1584

1. Define the Polynomial Using Lagrange Interpolation:

We start by defining the polynomial $P(x)$ using Lagrange interpolation. For $P(i) = 2^{a_i}$, the polynomial can be written as:
$$P(x) = \sum_{i=0}^n \frac{(x-0)(x-1)\cdots \widehat{(x-i)} \cdots (x-n)}{(i-0)(i-1)\cdots \widehat{(i-i)} \cdots (i-n)} \times 2^{a_i}$$
Here, the hat notation $\widehat{(x-i)}$ indicates that the term $(x-i)$ is omitted from the product.

2. Ensure Integer Coefficients:

To ensure that $P(x) \in \mathbb{Z}[x]$, we need to handle the denominators. We can multiply $P(x)$ by a sufficiently large power of 2, say $2^a$, to clear the denominators:
$$2^a \times P(x) = \sum_{i=0}^n \frac{2^a (x-0)(x-1)\cdots \widehat{(x-i)} \cdots (x-n)}{(i-0)(i-1)\cdots \widehat{(i-i)} \cdots (i-n)} \times 2^{a_i}$$
This ensures that $2^a \times P(x) \in \mathbb{Z}[x]$ and $2^a \times P(i)$ are still distinct powers of 2.

3. Factorize the Denominators:

Let $(i-0)(i-1)\cdots(i-n) = 2^{b_i} \times M_i$, where $M_i$ is an odd number. Then, we can rewrite $P(x)$ as:
$$P(x) = \sum_{i=0}^n \frac{(x-0)(x-1)\cdots \widehat{(x-i)} \cdots (x-n)}{M_i} \times 2^{a_i - b_i}$$

4. Ensure Integer Coefficients with Modulo Condition:

The key is to ensure that $2^{a_i - b_i} \equiv 0 \pmod{M_i}$. This can be achieved by choosing $a_i$ such that $a_i - b_i$ is sufficiently large. Specifically, we can choose $a_i = c_i + d_i \times \phi(M_i)$, where $\phi$ is Euler's totient function, and $d_i$ are natural numbers ensuring $a_i$ are distinct.

5. Construct the Polynomial:

Choose a sufficiently large constant $C$ and natural numbers $d_i$ such that $a_i = C + d_i \times \phi(M_i)$ are distinct. This ensures that $P(x)$ has integer coefficients and the numbers $P(0), P(1), \ldots, P(n)$ are distinct powers of 2.

6. Ensure Non-Vanishing Leading Term:

Finally, choose $d_n$ large enough compared to other $d_i$ to ensure that the $n$-th degree term does not vanish, making $P(x)$ a polynomial of degree $n$.

$\blacksquare$