Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$:


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}$:
10^6

share|improve this question
1  
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
2  
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 17 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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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