Take the 2-minute tour ×

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?

share|improve this question
A more usual way to phrase this question would be to ask about the distribution of primes that are $1$ and $3$ mod $4$, respectively. Various things are known: It is very well known that they appear asymptotically with the same frequency. For more subtle aspects a relevant key-word is "Shanks--Rényi race problem". (Depending on what happens in the interimm, I would give more details in a couple of hours.) –  quid Apr 19 '13 at 12:50
There is already a very nice article in the monthly about this :) jstor.org/stable/27641834 –  Gjergji Zaimi Apr 19 '13 at 12:53
@quid: according to some tests I made they seems to be "powerful enough" to pass random tests like "diehard" (starting from an initial random prime $p_i$) ... –  Vor Apr 19 '13 at 16:14
@Vor: I am sorry, I do not know anything about this test. There is a certain bias known to the quantity you are interested in. But closely related ones would be without that bias. For details please see my answer and in particular the mentioned papers; there is quite a bit information regarding distributiosn and alike. –  quid Apr 19 '13 at 19:46

1 Answer 1

up vote 9 down vote accepted

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 .

share|improve this answer
@quid: nice answer, I'll read (and try to understand :-) the suggested papers!!! thanks –  Vor Apr 19 '13 at 22:13
I'll add: starting at a specific prime $p_n$, there is a slight tendency for the bit-1 of the next prime $p_{n+1}$ to be the opposite of the bit-1 of $p_n$; basically, this is because $p_n+2$ gets first crack at being prime, before $p_n+4$ (and $p_n+6$ also gets its chance before $p_n+8$, etc.). However, this slight bias gets smaller and smaller as the primes involve increase. –  Greg Martin Apr 20 '13 at 0:23
@Vor: you are welcome. @Greg Martin: thank you for this additional information. –  quid Apr 20 '13 at 0:53
@quid, @Greg Martin, I downloaded the papers and started to read the Prime Number Races (it seems the math version of a E.A.Poe novel :-)))) ); just another quick question (I'm definitively not an expert in number theory): given an arbitrary $p_n$ and an integer $l$ can we prove anything about the probability to find two equal consecutive "bit #1" sequences of length $l$ among the $p_i, i\leq n$? (perhaps it is worth a new question on mathoverflow :-) –  Vor Apr 20 '13 at 10:17
@Vor: I am not sure what you are asking; but I think you mean finding a pattern of the form x...xy...y with $l$ repetitions for each. But, also I am not sure what the answer should be ;-). But I would assume that to prove something about the frequency of this could be very difficult; I mean for normal choices of $l$, say $l=1$ seems like a different type of problem, and also $l$ large relative to $n$ feels different, yet if say for $l=312$ and large $n$ anything can be proved is unclear to me (intuitively I doubt it, but I could well be wrong). What to expect, for this likely... –  quid Apr 20 '13 at 11:02

Your Answer


