# How to express the powers of two by a Diophantine equation?

Let $P_2:=\{2^k | k\in\mathbb N\}$ be the set of powers of two. I would like to "see" a polynomial $p(z_1,\ldots,z_r)$ with integer coefficients for which $P_2 =\{n\in\mathbb N | n=p(z_1,\ldots,z_r)\text{ with }z_1,\ldots,z_r\in\mathbb Z\}$. This should be possible, because $P_2$ is clearly recursively enumerable. If it should be easier to present such a polynomial for the set of powers of another prime number, or for the set of Fibonacci numbers, this would be sufficient for me as well.

-

Not exactly, as Jones considers $\{n\in \mathbb N\mid n=p(z_1,\ldots,z_r)\text{ with }z_1,\ldots,z_r\in\mathbb N\}$ instead. But of course this can easily be cured essentially by substituting $y$ with the sum of four squares. – Hagen von Eitzen Jun 9 '13 at 15:47