Is there a way to find the approximate value of the nth number?

Question

Is there a function that will return an approximate nth prime value? I think it will be something like an approximate inverse count function. For example, if I gave this function 25, it would return a number of about 100, or if I gave this function 1000, it would return a number of about 8000. I don't care if the number is returned simple or not, but I really want it should be fast (so there is no generation of the first n primes to return the nth.)

I wish I could generate the first n primes using a sieve ( Eratosthenes or Atkin ). Therefore, the approximation for n th will ideally never underestimate the value of the actual nth prime.

(Update: see my answer for a good method for finding the upper bound of the nth prime.)

Answer 1

More stringent restrictions:

static const unsigned short primes_small[] = {0,2,3,5,7,11}; static unsigned long nth_prime_upper(unsigned long n) { double fn = (double) n; double flogn, flog2n, upper; if (n < 6) return primes_small[n]; flogn = log(n); flog2n = log(flogn); if (n >= 688383) /* Dusart 2010 page 2 */ upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn)); else if (n >= 178974) /* Dusart 2010 page 7 */ upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn)); else if (n >= 39017) /* Dusart 1999 page 14 */ upper = fn * (flogn + flog2n - 0.9484); else /* Modified from Robin 1983 for 6-39016 _only_ */ upper = fn * ( flogn + 0.6000 * flog2n ); if (upper >= (double) ULONG_MAX) { /* Adjust this as needed for your type and exception method */ if (n <= 425656284035217743UL) return 18446744073709551557UL; fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1); } return (unsigned long) ceil(upper); } 

They should never be smaller than the actual nth_prime, should work for any 64-bit input and be an order of magnitude or closer compared to the formula from Robin given earlier (or Wimblik is a complicated formula with limited range). For my use, I have a slightly larger small column, so you can pull up the last estimate a bit. Technically, from the formulas, we could use floor () instead of ceil (), but I'm worried about accuracy.

Edit: Another option for improving this bit is to implement good graph boundaries (e.g. Axler 2014) and perform a binary search on them. My code for this method takes ~ 10 times longer than the above (still works in milliseconds), but can reduce the percentage of error by an order of magnitude.

If you need an estimate for the nth number, you can do:

• Cipolla 1902 (see Dusart 1999 page 12 or this document . I find three terms (m = 2) plus a third-order correction factor that is useful, but with a lot of members it fluctuates too much. The formula shown in the Wikipedia link is this formula (with m = 2). The two-term inverse or inverse Riemann R below will give better results.
• Calculate the upper and lower bounds of Dusart 2010 and average the results. Not so bad, although I suspect that using a weighted average will work better because the boundaries are not equally tight.
• li ^ {- 1} (n) Since li (n) is a decent approximation of a prime, the converse is a decent approximation of nth_prime. This and all the rest can be done quite quickly, like a binary function search.
• li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Closer as it approaches R (n)
• R ^ {- 1} The inverse Riemann function R is the nearest average approximation. I know what is reasonable.

Finally, if you have a very fast method for counting numbers, for example, one of the LMO implementations (now there are three open source implementations), you can write a quick, accurate nth_prime method. The calculation of the 10 ^ 10th number can be performed in a few milliseconds, and the 10-13th in a couple of seconds (on a modern fast machine). The approximations are extremely fast on all sizes and work for a much larger number, but everyone has a different idea of ​​what “big” means.

Answer 2

Thanks for all the answers. I suspected that there was something rather simple, but at that time I could not find it. I have done some more research.

As I want, for sieve to generate the first n prime numbers, I want the approximation to be greater than or equal to nth prime. (Therefore, I want an upper bound for the nth prime.)

Wikipedia gives the next upper bound for n >= 6

 p_n <= n log n + n log log n (1) 

where p_n is the nth right and log is the natural logarithm. This is a good start, but it can overestimate a small amount. This article in the College Journal of Mathematics gives a tighter upper bound for n >= 7022

 p_n <= n log n + n (log log n - 0.9385) (2) 

This is a much tougher binding, as shown in the following table.

 n p_n approx 1 error% approx 2 error% 1 2 10 29 31 6.90 100 541 613 13.31 1000 7919 8840 11.63 10000 104729 114306 9.14 104921 0.18 100000 1299709 1395639 7.38 1301789 0.16 1000000 15485863 16441302 6.17 15502802 0.11 10000000 179424673 188980382 5.33 179595382 0.10 

I applied the function of the nth first approximation to use the second approximation for n >= 7022 , the first approximation for 6 <= n < 7022 and search for an array for the first 5 primes.

(Although the first method is not a very tight binding, especially for the range in which I use it, I am not interested, since I want this for a sieve, and a sieve of lower numbers is cheaply calculated.)

Answer 3

The type number theorem gives a number of prime values ​​below the threshold value, so it could be used to give an approximate value for the nth prime number.

Answer 4

As a rough estimate, you can use n * ln (n) as an approximation for the nth prime. There is a much more complex but more accurate method, the details of which can be found on Wikipedia here .

Answer 5

My best prime (n) rating

 1/2*(8-8.7*nn^2+ 1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+ abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+ sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+ log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+ abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+ sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+ log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2)))))) 

Here is my latest experimental formula. By the way. Ten trillion prime numbers 323,780,508,946,331 this formula works pretty well on this scale, not sure if it keeps getting closer than n*ln(n)+n*(ln(ln(n))-0.9385) .

 1/2*(3-(8+ln(2.3))*nn^2+1/2*(-1+ abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+ (8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/ ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/ ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/ ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))* ln(ln((n*ln(8*n))/ln(n))/ln(2))))))) 

Answer 6

Effective implementation is probably not possible with a sieve. Think about what happens if you want to have the first 10,000 primes. You may have to make a sieve over a huge number of numbers.

Your own investment in this question and my answer are good ways to implement this without knowing appr, the meaning of simple

Answer 7

To complement Dana J Upper, this formula should give you a good bottom line.

 P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n; 

Answer 8

You can find the formula for finding the nth index using the prime theorem. Here's how https://azizl.imtqy.com Checkout in the first post