View Single Post
Old 2018-01-29, 00:50   #18
CRGreathouse's Avatar
Aug 2006

22·1,493 Posts

Originally Posted by a1call View Post
Actually it seems to me that the correct optimised range is neither

n!-n^2 < P < n!


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}.\]
CRGreathouse is offline   Reply With Quote