1
$\begingroup$

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

$2$ is the only prime with $1$ one, the Fermat primes are the only primes with $2$ ones, for $3$ ones we want primes of the form $2^a+2^b+1$ with $a>b$, so

$2^a+2^b+1=2^b(2^{a-b}+1)+1$, then

$2^a+2^b+2^c+1=2^c(2^{b-c}(2^{a-b}+1)+1)+1$,

and so on.

This would be a start if one hoped for the existence of infinitely many Fermat primes.

Edit: This paper proves that for all sufficiently large $t$ we can find a prime with exactly $t$ ones in their binary representation.

$\endgroup$
  • $\begingroup$ This seems to be open; see the related question Are There Primes of Every Hamming Weight? - MathOverflow $\endgroup$ – Chris Culter Jan 16 '15 at 9:49
  • $\begingroup$ Hope for infinitely many Fermat primes? I would be happy with just six of them. $\endgroup$ – Henning Makholm Jan 16 '15 at 9:51
  • $\begingroup$ @HenningMakholm I'm perfectly happy with five, all I hope for is some positive integer $k$. I don't think any of the primes for $k>2$ have a name, which is why I cited the possibility of infinity many Fermat primes. $\endgroup$ – Jaycob Coleman Jan 16 '15 at 9:56
  • $\begingroup$ @ChrisCulter A reference from that thread actually proves the existence of $k$. $\endgroup$ – Jaycob Coleman Jan 17 '15 at 1:11
  • $\begingroup$ @JaycobColeman That's a really interesting paper! I might be reading it wrong, but I don't think it proves the desired result. In Theorem 1.1, it's not immediately obvious how the estimate behaves for fixed $k$ (in their notation) and increasing $x$. At the end of the first section, the authors mention that their method doesn't help to bound tail distributions that are even broader than the count you're looking for. $\endgroup$ – Chris Culter Jan 17 '15 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.