Skip to main content
2 of 5
new links, edit suggested by jdh
dakota
  • 593
  • 5
  • 7

Are There Primes of Every Hamming Weight?

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}$?

dakota
  • 593
  • 5
  • 7