# Parity of primes [duplicate]

While working on a completely different (combinatorial) problem, I ran a simple program to calculate the parity of the first ~50000 primes (number of 1s in their binary representation modulo 2). The following graph summarizes the result: The number of primes having even parity seems to grow slower.

Is there a math explanation ?

I looked to the correspoding OEIS entry, but it doesn't provide any detail.

• What does "parity" mean? The parity of the number of ones in the binary representation? If so, please say it. If not, please say it. – Igor Rivin Oct 22 '14 at 18:46
• @IgorRivin: sorry, question edited (I had only one non-trivial definition of parity of a number in my mind :-) – Marzio De Biasi Oct 22 '14 at 18:54
• It's right there on the right hand side under "Related". mathoverflow.net/questions/44561/odd-bit-primes-ratio – Felipe Voloch Oct 22 '14 at 18:57
• @FelipeVoloch: thanks, I didn't notice it while typing the question (or perhaps it wasn' there) :-S ... a.k.a. the Thue-Morse numbers ... – Marzio De Biasi Oct 22 '14 at 19:00
• A version of this question was earlier explored in "Odd-bit primes ratio." – Joseph O'Rourke Oct 22 '14 at 19:36

## 1 Answer

It was shown (amongst other things) by Gel'fond that the asymptotic growth rates of the primes with even and odd parity base 2 expansions are the same:

Gelʹfond, A. O. Sur les nombres qui ont des propriétés additives et multiplicatives données. (French) Acta Arith. 13 1967/1968 259–265.

A more recent paper on this is due to Mauduit and Rivat.

• I've noticed that most primes seem to start with a 1 in their base 2 expansion. – Anthony Quas Oct 22 '14 at 18:58
• OK, so, asymptotically they are the same, but that doesn't rule out the possibility that odd parity up to $N$ exceeds even for all $N$. It doesn't even exclude the possibility that the difference goes to infinity. Do the published results speak to these more delicate questions? – Gerry Myerson Oct 22 '14 at 22:16
• It is known that among multiples of 3, asymptotically half of them have an even number of 1s in their binary expansion, but there is a second-order term that biases multiples of 3 towards having an even number of 1s. (At its core, this is because a multiple of 3 must have its alternating sum of bits be a multiple of 3; this is more likely when there are the same number of even-bit 1s and odd-bit 1s than when there are 3 more even-bit 1s than odd-bit 1s, etc.) ... – Greg Martin Oct 22 '14 at 22:32
• ... Presumably then, the bias in the above graph is due (to first-order approximation) to the fact that primes are not multiples of 3. This phenomenon has been explored by V. Shevelev (see papers on the arXiv). – Greg Martin Oct 22 '14 at 22:32
• It seems too that most primes end with a $1.$ It is rare to have all $1's$ but even rarer to only have that pair of $1$s..... – Aaron Meyerowitz Oct 23 '14 at 7:52