# Odd-bit primes ratio

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$$: (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}$$: • 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. – Qiaochu Yuan Nov 2 '10 at 14:58
• I guess the 2.5% bias in favor of odd-bit primes in the first 100K is just an unexplainable fact about the distribution...? – Joseph O'Rourke Nov 2 '10 at 15:18
• What you call "odd-bit numbers" are often called Thue-Morse numbers. I like your terminology better, but tradition is tradition. – Kevin O'Bryant Nov 4 '10 at 3:08
• I thought the "odd-bit numbers" were usually called odious numbers (and the complementary set called evil numbers). – David Eppstein Oct 31 '11 at 21:51
• I believe we have Berlekamp, Conway, and Guy, Winning Ways, to thank for the "odious" and "evil" terminology. – Gerry Myerson Aug 12 at 22:46

## 2 Answers

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.

• Beat me by 23 seconds. +1 for that. – Charles Nov 2 '10 at 14:48
• This looks rather analogous to Chebotarev's theorem. – Sylvain JULIEN Aug 12 at 20:44

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.

• 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! – Joseph O'Rourke Nov 2 '10 at 16:16