Is there anything known/proved/conjectured about the distribution of:
$$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$
i.e. the bit 1 of the binary representation of the $n$-th prime number?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIs there anything known/proved/conjectured about the distribution of:
$$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$
i.e. the bit 1 of the binary representation of the $n$-th prime number?
First, I strongly second the recommendation of Gjergji Zaimi to read the paper by Granville and Martin; here is a link to the arXiv version in addition.
Some initial and partial information:
On a very rough scale the frequency counts of primes with "bit 1" equal to $0$ and $1$, resp., are the same; both counting functions are asymptotic to $\frac{1}{2} \text{li}(x)$ with error terms essentially as commonly know from the prime counting function. This is the well-know Prime Number Theorem for arithmetic progressions, as the condition on the 'bit 1' translates into considering primes congruent to $1$ and $3$ modulo $4$ respectively.
However, if one compares the exact counts of primes congruent to $1$ and $3$ modulo $4$ respectively, let us call the respective counting functions $\pi_1(x)$ and $\pi_3(x)$, then one notes (at least at the start) that there are more congruent to $3$ than congruent to $1$, so $\pi_3(x) > \pi_1(x)$, an observation made by Chebyshev. However, Littlewood showed that the difference $\pi_3(x) - \pi_1(x)$ can also be negative, and even is infinitely often essentially as negative as it can get (under the assumption that both should not deviate from $\text{li}(x)/2$ by more than $\sqrt{x}$ and a little).
So, now one might think that one just came across a phenomenon of small numbers with this initial bias however this is not so there is a bias in the distribution.
If one defines $P$ to be the set of all integers such that $\pi_3(x) > \pi_1(x)$ then these are not "half of the integers".
Rubinstein and Sarnak proved (under widely believe conjectures on zeros of L-functions, GRH and GSH) that the logarithmic density of this set, that is the limit of
$$
\frac{1}{\log x} \sum_{n \in P} \frac{1}{n}
$$
is $0.9959...$, so quite close to $1$.
But, if one would keep to look at the "bit 1" yet restrict to those primes with "bit 2" equal to $1$ this bias goes away!
This might seem quite odd when said like this, it becomes somewhat less mysterious (though of course stays fascinating) if one observes the following:
The primes with "bit 2" equal to $1$ are those congruent to $5$ and $7$ modulo $8$ (except for $2$ of course).
And, the bias in the case of $1$ and $3$ modulo $4$ is roughly speaking due to the fact that all squares of odd primes are $1$ modulo $4$,
while for $5$ and $7$ modulo $8$ squares of primes are to be found in neither of the two classes.
As said the above mentioned paper provides a lot more information related to these phenomena; also the introduction of the paper of Rubinstein and Sarnak provides a very good overview. And, there is also more recent work related to this see for example http://arxiv.org/abs/1108.5342
Also, the result of Rubinstein and Sarnak is conditional; for discussion of getting (partially) rid of these assumptions, or it is perhaps more precise to say working somehow under the negation of the assumtptions, see again the already mentioned paper or, e.g., this recent contribution http://arxiv.org/abs/1204.6715 .