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?

  • 1
    $\begingroup$ 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.) $\endgroup$
    – user9072
    Apr 19, 2013 at 12:50
  • 2
    $\begingroup$ There is already a very nice article in the monthly about this :) jstor.org/stable/27641834 $\endgroup$ Apr 19, 2013 at 12:53
  • $\begingroup$ @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$) ... $\endgroup$
    – Vor
    Apr 19, 2013 at 16:14
  • $\begingroup$ @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. $\endgroup$
    – user9072
    Apr 19, 2013 at 19:46

1 Answer 1


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 .

  • $\begingroup$ @quid: nice answer, I'll read (and try to understand :-) the suggested papers!!! thanks $\endgroup$
    – Vor
    Apr 19, 2013 at 22:13
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 20, 2013 at 0:23
  • $\begingroup$ @Vor: you are welcome. @Greg Martin: thank you for this additional information. $\endgroup$
    – user9072
    Apr 20, 2013 at 0:53
  • $\begingroup$ @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 :-) $\endgroup$
    – Vor
    Apr 20, 2013 at 10:17
  • $\begingroup$ @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... $\endgroup$
    – user9072
    Apr 20, 2013 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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