0
$\begingroup$

Let $b$ be any prime. Consider a set of $b-1$ buckets. Consider all prime numbers (except $b$) up to some $N$. Let us do the simple hash wherein each prime $x$ less than $N$ is assigned to the $x \bmod b$-th bucket.

  1. It is found that as $N$ increases, the number of primes getting assigned to the $b-1$ buckets get very close to each other very rapidly. Can this rapid reduction in the range of numbers of primes hashing to each bucket be quantified as a function of $N$ and $b$?

Note: If $b$ is not a prime, then, some of the buckets do not receive any of the primes (for example, if $b = 8$, for any prime $x$, $x \bmod 8$ can never be $2$ and bucket number $2$ remains empty) but even then, those buckets with non-zero numbers of primes tend to have very nearly equal numbers of primes (from the comment below from Pedraig O'Cathain, I understand, the numbers of primes in each bucket getting close follows from the 'prime number theorem for arithmetic progressions').

  1. Consider the special case $b =7$ and a specific value of the remainder, say $3$. Only for those primes that gave hash value (remainder) $3$, we looked at the buckets into which the next higher prime would go. It was found that for primes immediately greater than those that hash to $3$, their distribution among the buckets is always uneven (i.e., if a prime hashes to $3$, the next prime is not equally likely to hash to each possible value $1$ to $6$) and never seems to equalize among the buckets even if we go to very large $N$. If bucket $b_i$ gets more primes than bucket $b_j$ for some value of $N$, then $b_i$ continues to get more primes for larger values of $N$; however, the ratio of number of primes in $b_i$ to number in $b_j$ reduces with $N$ but never quite gets to $1$ it seems. Have these phenomena been quantified?

Note: Also checked numerically the buckets to which the second prime after a prime that hashes to bucket 3 goes. Now, the range of probabilities among the 6 possible buckets is much reduced but for even fairly large N, they don't quite equalize.

  1. Is there some hash function for primes that has the property: if any prime hashes to a particular bucket, the next higher prime is equally likely to hash to any of the buckets?
Improve this question
$\endgroup$
8
  • 7
    $\begingroup$ Granville and Martin wrote a paper where this is discussed: arxiv.org/pdf/math/0408319.pdf They explain many details of the behaviour of these 'prime races'. Some buckets are fuller than others most of the time, as you have observed. They can quantify by how much some buckets lead, and how often. The tie all this to the Riemann hypothesis - it's a really nice paper. $\endgroup$
    – Padraig Ó Catháin
    Commented Mar 20 at 18:50
  • 4
    $\begingroup$ Writing $b$-1 instead of $b-1$ is definitely incorrect usage in MathJax or LaTeX. That has been edited above. $\endgroup$
    – Michael Hardy
    Commented Mar 20 at 19:21
  • 2
    $\begingroup$ As for the question of dependence of a prime on the previous prime, see Robert J Lemke Oliver and Kannan Soundararajan, Unexpected biases in the distribution of consecutive primes, Proc Nat Acad Sci 113 #31 (2016) E4446-E4454, available at pnas.org/doi/full/10.1073/pnas.1605366113. Abstract next comment. $\endgroup$
    – Gerry Myerson
    Commented Mar 21 at 6:00
  • 3
    $\begingroup$ Prime numbers ... are well known to be very well distributed among the reduced residue classes $\bmod q$. Surprisingly, the same does not appear to be true for sequences of consecutive primes, with different patterns occurring with wildly different frequencies. We formulate a precise conjecture, based on the Hardy−Littlewood conjectures, which explains this phenomenon. In particular, we predict that all patterns do occur their fair share of the time in the limit, but that there are secondary terms only very slowly tending to zero that create the observed biases. $\endgroup$
    – Gerry Myerson
    Commented Mar 21 at 6:03
  • 1
    $\begingroup$ Doesn't the paper of Oliver and Soundararajan answer question 3, at least conjecturally? "...we predict that all patterns do occur their fair share of the time in the limit...." $\endgroup$
    – Gerry Myerson
    Commented Mar 22 at 0:29

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .