View Single Post
2018-01-29, 00:50   #18
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by a1call Actually it seems to me that the correct optimised range is neither n!-n^2 < P < n! Nor n!-n^2 < P < n!-1 But rather n!-n^2 < P < n!-n Since none of the integers m such that n!-n <= m < n! -1 Can be prime.
Right, you can take the upper bound as n!-n or n!-1.

Either way you have ~ n^2 numbers of size roughly n! which are divisible by none of the primes up to n. Heuristically this makes them
$\prod_{p\le n}\frac{p}{p-1} \approx e^{-\gamma}\log n$
times more likely to be prime than the average prime of its size, for an overall probability of
$\frac{e^{-\gamma}\log n}{\log n!} \approx \frac{e^{-\gamma}\log n}{n\log n} = \frac{e^{-\gamma}}{n}$
and an expected
$\frac{n^2}{\log(n^2)}\cdot\frac{e^{-\gamma}}{n} = \frac{e^{-\gamma}n}{2\log n}$
primes in the interval. The chance of having none is then
$\exp\left(-\frac{e^{-\gamma}n}{2\log n}\right)$
and since
$\int\exp\left(-\frac{e^{-\gamma}n}{2\log n}\right)$
converges there should be only finitely many you'd expect only finitely many intervals without primes. A quick check shows that the first 500 have primes, making the odds of any being empty around
$\int_{500.5}^{\infty}\exp\left(-\frac{e^{-\gamma}n}{2\log n}\right) \approx 4\cdot10^{-9}.$