Are There Primes of Every Hamming Weight?

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.

For this context, though not so highbrow: Wagstaff, Prime Numbers with a Fixed Number of One Bits or Zero Bits in Their Binary Representation, Experiment Math 10 (2001), 267-273.

http://www.expmath.org/restricted/10/10.2/wagstaff.ps

Standard heuristics on the distribution of primes indicate that there should be infinitely many primes of each Hamming weight $h \ge 3$. If that is true, together with the fact that 2 has weight one and 3 has weight two, you get a positive answer to your question. Turning these heuristics into a proof is likely to be very impossible with current "technology". So it's quite amazing that the proof described in Ben Green's answer exists.

Details of the heuristic. Fix a hamming weight $h \ge 3$. Let's look at integers of Hamming weight $h$ of the form $2^n + \sum_{j=1}^{h-2} 2^{a_j} + 1$, where $0 < a_1 < \cdots < a_{h-2} < n$. There are $n-1\choose{h-2}$ such integers and the probability of each of them being composite is $1-1/n\log 2$. If (BIG IF) these probabilities are independent then you expect that the probability of them all being composite is very small and you expect there to be primes of that form for infinitely many (or even all sufficiently large) $n$.