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:

enter image description here

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.

  • $\begingroup$ 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. $\endgroup$ – Igor Rivin Oct 22 '14 at 18:46
  • $\begingroup$ @IgorRivin: sorry, question edited (I had only one non-trivial definition of parity of a number in my mind :-) $\endgroup$ – Marzio De Biasi Oct 22 '14 at 18:54
  • 2
    $\begingroup$ It's right there on the right hand side under "Related". mathoverflow.net/questions/44561/odd-bit-primes-ratio $\endgroup$ – Felipe Voloch Oct 22 '14 at 18:57
  • $\begingroup$ @FelipeVoloch: thanks, I didn't notice it while typing the question (or perhaps it wasn' there) :-S ... a.k.a. the Thue-Morse numbers ... $\endgroup$ – Marzio De Biasi Oct 22 '14 at 19:00
  • 1
    $\begingroup$ A version of this question was earlier explored in "Odd-bit primes ratio." $\endgroup$ – Joseph O'Rourke Oct 22 '14 at 19:36

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.

  • 14
    $\begingroup$ I've noticed that most primes seem to start with a 1 in their base 2 expansion. $\endgroup$ – Anthony Quas Oct 22 '14 at 18:58
  • $\begingroup$ 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? $\endgroup$ – Gerry Myerson Oct 22 '14 at 22:16
  • 1
    $\begingroup$ 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.) ... $\endgroup$ – Greg Martin Oct 22 '14 at 22:32
  • $\begingroup$ ... 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). $\endgroup$ – Greg Martin Oct 22 '14 at 22:32
  • $\begingroup$ 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..... $\endgroup$ – Aaron Meyerowitz Oct 23 '14 at 7:52

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