Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this?
Edit: what happens if we limit the case to the prime number of the form $4k+1$ where k is a natural number?
Edit: it's fine to replace approximate prime number with finding any prime number that is bigger than the given prime number in a time-efficient way.
On
well.. an exact calculation could be provided by: $p(n)=(f(n-1)/f(n))*(p(n-1)-1)$ where f(n) is defined as $π(n)$ in this question: Expected smallest prime factor
Well besides that an approximation of the previous formula could be: $ p(n)=(ln(n+1)/ln(n-1))*((ln(n)-ln(n-1))/(ln(n+1)-ln(n))*(p(n-1)-1)$
I will come back with some more infos.
I hope i've helped
You could use the fact that the density of primes around $p$ is about $\frac 1{\ln p}$ to say the next is around $p + \ln p$, but the variance on this estimate is huge. For $4k+1$ primes, the density is about the same as $4k+3$ primes, so the estimate would be $p + 2 \ln p$.
To find the next, just start from $p$ and check all numbers of the form $6k+1$ or $6k+5$ until you find one. You shouldn't have to check toooo many. (On average, $\frac {\ln p}3$)
To find any larger prime, just search the Web for the largest known prime.