Does there exist a polynomial $f$ with integer coefficients such that for every natural number $n$, $f(0) , f(1) ... f(n) $ are all distinct powers of 2 ?
I have no clue about how should I start thinking about this problem but I felt that it is very interesting.
Claim: There is no polynomial $f(x)$ with integer coefficients whose values at all non-negative integers are distinct powers of $2$.
Proof by contradiction: Let $m$ be the smallest power of $2$ attained by $f(x)$ when evaluated at positive integers, so that:
But that implies $f(v)$ is divisible by $2m$ too; a contradiction.
Claim: For every $n\geq 0$, there is a polynomial $f_n(x)$ with integer coefficients, such that $f(0), f(1), \ldots, f(n)$ are all distinct powers of $2$.
Proof by construction: Let $n! = 2^m\times r$, with $r$ odd and $q=2^{\varphi(r)}$ and let
$$f_n(x)=2^m\times \sum_{k=0}^n \binom{x}{k}(q-1)^k$$
Clearly, $f_n(x)$ is a polynomial of degree $n$. Evaluating it for $0\leq x\leq n$ yields: $$f(x) = 2^m\times \sum_{k=0}^n \binom{x}{k}(q-1)^k = 2^m\times \sum_{k=0}^x \binom{x}{k}(q-1)^k = 2^m\times q^x = 2^{m+x\varphi(r)}$$ so the values of the polynomial for $0\leq x\leq n$ are indeed powers of $2$. In order to prove that it has integer coefficients, we can write $$2^m\binom{x}{k}(q-1)^k = \frac{2^m (q-1)^k}{k!}\prod_{i=0}^{k-1}(x-i)$$ This is trivially seen to be integer if $k=0$. For $k\geq 1$, the numerator is divisible by $2^m$ and also by $r$; since it's multiple of $(q-1)$, which Euler's generalization of Fermat's Little Theorem shows to be multiple of $r$. But being divisible by both $2^m$ and $r$ implies divisibility by $n!$ which, in turn, implies divisibility by $k!$. Thus, the polynomial's coefficients are indeed integers, as we required.
Note: The value of $q$ used in preceding proof is often unnecessarily large; it's sufficient for $k!$ to divide $2^m(q-1)^k$ while the value used in proof guarantees divisibility of $2^m(q-1)$. For example, for $n=12$, the proof-used value of $q$ would be $2^{194400}$, while $q=2^{60}$ would work just as well. The value of $m$ can sometimes be lowered too (e.g. for $n=12$, it's sufficient to take $m=8$ rather than $m=10$ based on the proof), but unlike the lower $q$, this is not easily seen from the proof.