19
$\begingroup$

Say that a number is an odd-bit number if the count of 1-bits in its binary representation is odd. Define an even-bit number analogously. Thus $541 = 1000011101_2$ is an odd-bit number, and $523 = 1000001011_2$ is an even-bit number.

Are there, asymptotically, as many odd-bit primes as even-bit primes?

For the first ten primes, we have $$ \lbrace 10, 11, 101, 111, 1011, 1101, 10001, 10011, 10111, 11101 \rbrace $$ with 1-bits $$ \lbrace 1, 2, 2, 3, 3, 3, 2, 3, 4, 4 \rbrace $$ and so ratio of #odd to $n$ is $5/10=0.5$ at the 10-th prime. Here is a plot of this ratio up to $10^5$:


10^5
(Vertical axis is mislabeled: It is #odd/$n$.)


I would expect the #odd/$n$ ratio to approach $\frac{1}{2}$, except perhaps the fact that primes ($>2$) are odd might bias the ratio. The above plot does not suggest convergence by the 100,000-th prime (1,299,709).

Pardon the naïveness of my question.

Addendum: Extended the computation to the $10^6$-th prime (15,485,863), where it still remains 1.5% above $\frac{1}{2}$:


10^6


$\endgroup$
13
  • 1
    $\begingroup$ The fact that primes greater than 2 are odd only biases one bit, which should have a negligible effect in the long run. Ignoring the last bit, looking at any particular finite subset of the bits should reveal a uniform distribution by the strong form of Dirichlet's theorem and the difficult question is whether this is still true if one looks at all the bits. $\endgroup$ Nov 2, 2010 at 14:58
  • 1
    $\begingroup$ I guess the 2.5% bias in favor of odd-bit primes in the first 100K is just an unexplainable fact about the distribution...? $\endgroup$ Nov 2, 2010 at 15:18
  • 2
    $\begingroup$ What you call "odd-bit numbers" are often called Thue-Morse numbers. I like your terminology better, but tradition is tradition. $\endgroup$ Nov 4, 2010 at 3:08
  • 8
    $\begingroup$ I thought the "odd-bit numbers" were usually called odious numbers (and the complementary set called evil numbers). $\endgroup$ Oct 31, 2011 at 21:51
  • 2
    $\begingroup$ I believe we have Berlekamp, Conway, and Guy, Winning Ways, to thank for the "odious" and "evil" terminology. $\endgroup$ Aug 12, 2019 at 22:46

2 Answers 2

24
$\begingroup$

Yes. This was proven in

C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. Math.

I found this by searching for "evil prime" and "odious prime" in the OEIS. More precisely, they prove the Gelfond conjecture:

Let $s_q(p)$ denote the sum of the digits of $p$ in base $q$. For $m, q$ with $\gcd(m, q-1) = 1$ there exists $\sigma_{q,m} > 0$ such that for every $a \in \mathbb{Z}$ we have

$$| \{ p \le x : s_q(p) \equiv a \bmod m \} | = \frac{1}{m} \pi(x) + O_{q,m}(x^{1 - \sigma_{q,m}})$$

where $p$ is prime and $\pi(x)$ the usual prime counting function.

$\endgroup$
2
  • $\begingroup$ Beat me by 23 seconds. +1 for that. $\endgroup$
    – Charles
    Nov 2, 2010 at 14:48
  • $\begingroup$ This looks rather analogous to Chebotarev's theorem. $\endgroup$ Aug 12, 2019 at 20:44
21
$\begingroup$

Yes, the ratio approaches 1/2. This was proven in

C. Mauduit et J. Rivat, Sur un probléme de Gelfond: la somme des chiffres des nombres premiers.

See Three topics in additive prime number theory for exposition. Also, the poorly-named sequences in Sloane: A027697 and A027699.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks! There is a nice conjecture of Vladimir Shevelev embedded in the OEIS descriptions: the n-th odius prime is less than the n-th evil prime. I agree that these are poorly named! $\endgroup$ Nov 2, 2010 at 16:16
  • 1
    $\begingroup$ @JosephO'Rourke Indeed. But it seems to me that several of those conjectures are "false", due to Mauduit & Rivat. For example, it cannot be true that A027699(n) - A027697(n) tends to infinity with n. $\endgroup$
    – Klangen
    Sep 26, 2022 at 6:37
  • $\begingroup$ @Klangen Perhaps you could submit that as a comment to those sequences? $\endgroup$
    – Charles
    Sep 26, 2022 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.