is this prime probability function that generated from Eratosthenes Sieve can predict numbers of prime in closed interval?

60 Views Asked by At

I have two question regarding this prime probability $P(p)$ for $p$ that exists for $[p_{k-1}^2 , x]$

$P(p)=\prod^k_{i=1}\big{(} 1 -\frac{1}{p_i}\big{)}$

Where $x<p_k^2$ and $k$ was index such that $p_1=2$, $p_2=3$ and so on.


  1. Is it trivial probability function of prime for the interval? Or it's not working because prime wasn't equally distributed enough even in $[p_{k-1}^2, p_k^2]$ or there was another reason so it doesn't work?

  2. Secondly, if this works and i want to use $P(p)$ into my proof works, did i need to proof the probability first?

I'm trying looking into this but didn't find the answer. I hope my question was clear enough.

1

There are 1 best solutions below

3
On

This probability $P(p)$ is a reasonable heuristic for the probability that a random number in $[p_{k-1}^2,x]$ is prime, but it doesn't actually equal the probability.

This number was presumably derived using the fact that the probability that $p_i$ divides a "randomly chosen number" is $1/p_i$, and then multiplying together the probability that $p_i$ doesn't divide a randomly chosen number across all $i$. The first (less pressing) issue is that the probability isn't exactly $1/p_i$ if you're choosing the number from an interval of a length that isn't a multiple of $p_i$. This isn't a terrible issue, but it is definitely important; we can't have all of our primes dividing the length of $[p_{k-1}^2,x]$, since $p_1\cdots p_{k-1}$ is very large.

The second issue is that the events "divisible by $p_i$" and "divisible by $p_j$" aren't independent. They are likely roughly independent (and are independent if $p_ip_j$ divides the length of your interval), but for a smaller interval it's possible to get unlucky and have one number that has a lot of prime factors, or for your prime factors to be more spread out than normal. These events are both hard to estimate and quantify.

In sum, $P(p)$ doesn't actually equal the probability that a number in your interval is prime -- for it to equal the probability that no small prime divides a random number, your interval would need to be much, much larger, and numbers in such an interval will have too many possible prime factors.