How many integers?

Since $2^{1000} \equiv 1$ modulo $3$ , if we define $b = \tfrac{1}{3}(2^{1000}-1)$ then the quadratic polynomial $f_0(x) \; = \; 1-b + bx^2$ is such that $f_0(n) = n^{1000}$ for $n=-2,-1,1,2$ .

Suppose that $f(x)$ was a cubic polnomial with real coefficients such that the equation $f(n) = n^{1000}$ has five or more distinct real roots. Then the polynomial $g(x) = x^{1000} - f(x)$ would have at least five distinct real zeros. Rolle's Theorem tells us that $g'(x)$ would have at least four distinct real zeros, $g''(x)$ at least three distinct real zeros, and $g'''(x)$ at least two distinct real zeros.

However, if $f(x) = ax^3 + bx^2 + cx + d$ , then $g'''(x) \; = \; 1000\times999\times998x^{997} - 6a$ which (since $997$ is odd) has exactly one real real root.

Thus no cubic polynomial can be found which satisfies the equation $f(n) = n^{1000}$ five or more times, and so 4 is the largest possible number. Whether or not the polynomial $f(x)$ has integer coefficients, or whether the values of $n$ are integers, is irrelevant.

Consider the polynomial:

$f(x) = ax^3 + x^2 - ax, \ a = \frac{2^{999} - 2}3$

Clearly $f(0) = 0, f(1) = 1, f(-1) = 1$ and $f(2) = 6a + 4 = 2^{1000}$ . Hence $f(n) = n^{1000}$ at four distinct points: $n = -1, 0, 1, 2$ .

On the other hand, suppose there exists a cubic polynomial $f(x)$ such that $f(x) = x^{1000}$ at five distinct real values $a_1 < a_2 < \ldots < a_5$ . Thus, $g(x) := x^{1000} - f(x)$ has roots $a_i$ and by Rolle's theorem, for $i=1,2,3,4$ , we can find $b_i$ satisfying $a_i < b_i < a_{i+1}$ such that the derivative of g disappears.

By the same reasoning, we can find distinct $c_1 < c_2 < c_3$ at which $g''(x) = 1000\cdot 999 x^{998} - f''(x)$ disappears. And also $d_1 < d_2$ at which $g'''(x) = 1000\cdot 999\cdot 998 x^{997} - f^{(3)}(x)$ disappears. But $f^{(3)}$ is constant and $x^{997}$ is a strictly increasing function, so this is impossible.