That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?
In this case, the Hamming weight of a number is the number of $1$s in its binary expansion.
Many problems of this sort have been considered, but perhaps not in such language. For instance, the question "Are there infinitely many Fermat primes?" corresponds to asking, "Are there infinitely many distinct primes with Hamming weight exactly $2$?" Also related is the question of whether there are infinitely many Mersenne primes.
These examples suggest a class of such problems, "Do there exist infinitely many primes which are the sum of exactly $n$ distinct powers of two?"
Since this question is open even for the $n=2$ case, I pose a much weaker question here.
What is known is that for every $n \leq 1024$ there is such a prime.
The smallest such prime is listed in the Online Encyclopedia of Integer Sequences A061712.
The number of zeros in the smallest such primes are listed in A110700. The number of zeros in a number with a given Hamming weight is a reasonable measure of how large that number is. The conjecture at OEIS is quite a bit stronger than the question I pose.
Is there a theorem ensuring such primes for every $n \in \mathbb{Z}_{>0}$?
Best Answer
Fedja is absolutely right: this has been proven, for sufficiently large $n$, by Drmota, Mauduit and Rivat.
Although it looks at first sight as though this question is as hopeless as any other famous open problem on primes, it is easy to explain why this is not the case. Of the numbers between $1$ and $N := 2^{2n}$, the proportion whose digit sum is precisely $n$ is a constant over $\sqrt{\log N}$. These numbers are therefore quite "dense", and there is a technique in prime number theory called the method of bilinear sums (or the method of Type I/II sums) which in principle allow one to seriously think about finding primes in such a set. This is what Drmota, Mauduit and Rivat do.
I do not believe that their method has currently been pushed as far as (for example) showing that there are infinitely many primes with no 0 when written in base 1000000.
Let me also remark that they depend in a really weird way on some specific properties of these digit representation functions, in particular concerning the sum of the absolute values of their Fourier coefficients, which is surprisingly small. That is, it is not the case that they treat these Hamming sets as though they were "typical" sets of density $1/\sqrt{\log N}$.
I think one might also mention a celebrated paper of Friedlander and Iwaniec, http://arxiv.org/abs/math/9811185. In this work they prove that there are infinitely many primes of the form $x^2 + y^4$. This sequence has density just $c/N^{1/4}$ in the numbers up to $N$, so the analysis necessary to make the bilinear forms method work is really tough. Slightly later, Heath-Brown adapted their ideas to handle $x^3 + 2y^3$. Maybe that's in some sense the sparsest explicit sequence in which infinitely many primes are known (except of course for silly sequences like $s_n$ equals the first prime bigger than $2^{2^n}$).
Finally, let me add the following: proving that, for some fixed $n$, there are infinitely many primes which are the sum of $n$ powers of two - this is almost certainly an open problem of the same kind of difficulty as Mersenne primes and so on.