Take the 2-minute tour ×

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 $5/5=1$ at the 10-th prime. Here is a plot of this ratio up to $10^5$:


I would expect the 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}$:

share|improve this question
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
@Kevin: Thanks for the key phrase! Wikipedia says: "The Thue–Morse sequence was first studied by Eugène Prouhet in 1851,.... However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906." Quite a long and tangled history! –  Joseph O'Rourke Nov 4 '10 at 12: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

2 Answers 2

up vote 18 down vote accepted

Yes. This was proven in

C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chires 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.

share|improve this answer
Beat me by 23 seconds. +1 for that. –  Charles Nov 2 '10 at 14:48
Thanks, Qiaochu & Charles for your quick answers! –  Joseph O'Rourke Nov 2 '10 at 14:57

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.

share|improve this answer
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

Your Answer


