4
$\begingroup$

Suppose you are sorting all of the prime numbers between $1$ and some large number $N$, from smallest to largest; into buckets which correspond to their residue classes modulo some prime $p_i$.

Now suppose you actually had two copies of the prime numbers between $1$ and some large number $N$; one to be sorted by residue classes modulo prime $p_i$, and the other to be sorted by residue classes modulo prime $p_{i+1}$.

At each step in time you place the smallest prime number and its copy into the two buckets as instructed above.

At what point in time can you be sure that, all of the buckets that correspond to residue classes of $p_i$ (excluding bucket $[0]_i$) contain more prime numbers than any of the buckets corresponding to residue classes of $p_{i+1}$.

Or can you never be sure?

$\endgroup$
  • $\begingroup$ By Bertrands postulate, and random distribution ( not really, as some residues depend on multiplier), you get each residue class mod the later primes is over half the amount in any residue mod the former. $\endgroup$ – Roddy MacPhee Sep 29 at 13:53
  • 2
    $\begingroup$ It depends how elementary you want it to be. For a fixed pair $q_1,q_2$ the prime number theorem in arithmetic progressions is effective, you can compute (from the values of Dirichlet L-functions $\bmod q_i$ near $s=1$) a constant $C$ such that $\forall x$, for $q_i \nmid a$, $$|\sum_{p \le x, p \equiv a \bmod q_i} 1-\frac{x}{(p-1)\log x}| < C\frac{x}{\log^2 x}$$ I don't think there is a simple formula for $C(q)$ which would work for all $q$ $\endgroup$ – reuns Sep 29 at 19:13

Your Answer

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

Browse other questions tagged or ask your own question.