How to find smallest integer which is greater than N positive primes

782 Views Asked by At

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula:

PI(N) = N / Log(N)

But what about the reverse case? What if someone gives me the value of PI(N) (say 25) and asks me for the value of N. Is there a known formula for it?

Example: Upto which integer you must examine to find the first 168 primes? The answer is 1000.

2

There are 2 best solutions below

1
On BEST ANSWER

It's been known since the early 1960s that

$$n(\log n+\log\log n−3/2)<p_n<n(\log n+\log\log n-1/2)$$

for $n\gt19$, where $p_n$ denotes the $n$th prime. Of course all this says, for the example the OP gave, is

$$884\le p_{168}\le1051$$

(after rounding the decimals up and down, respectively). The fraction $3/2$ in the lower limit has been improved to $1$ for all $n$, so that we can say

$$968\le p_{168}\le1051$$

The fraction $1/2$ in the upper limit has also been improved (to $0.9484$), but only for large $n$ (i.e., $n\gt39017$).

5
On

This can be approximated by $f(n)=n\log n$ where the logarithm is natural (base $e$). A better approximation is $$ f_1(x)=x\log x+x\log\log x-x $$ and a still better approximation is the inverse logarithmic integral.

Taking your example of 168, the three methods give 860, 967, and 934. (Here the second is best, but once the numbers get past 50,000 or so the third one is better, and quickly becomes far better.)