I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
$\begingroup$
$\endgroup$
0
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
13
No, there is no known formula that gives the nth prime, except artificial ones you can write that are basically equivalent to "the $n$th prime". But if you only want an approximation, the $n$th prime is roughly around $n \ln n$ (or more precisely, near the number $m$ such that $m/\ln m = n$) by the prime number theorem. In fact, we have the following asymptotic bound on the $n$th prime $p_n$:
$n \ln n + n(\ln\ln n - 1) < p_n < n \ln n + n \ln \ln n$ for $n\ge{}6$
You can sieve within this range if you want the $n$th prime. [Edit: There are better ideas than a sieve, see the answer by Charles.]
Entirely unrelated: if you want to see formulae that generate a lot of primes (not the $n$th prime) up to some extent, like the famous $f(n)=n^2-n+41$, look at the Wikipedia article formula for primes, or Mathworld for Prime Formulas.
answered Jul 30, 2010 at 20:10
-
2$\begingroup$ It should be noted that this is derived from the prime number theorem. $\endgroup$ Jul 30, 2010 at 20:40
-
$\begingroup$ Right. I had omitted mentioning it, but thanks to your reminder I went and found a precise bound I hadn't previously seen. :-) $\endgroup$ Jul 30, 2010 at 20:58
-
$\begingroup$ I don't know why the downvote, but a closely related question was just posted (math.stackexchange.com/questions/940338/…) and perhaps it has gotten this topic some new attention. (I think your first sentence is a good summary conclusion, but someone else may disagree.) $\endgroup$– David KSep 22, 2014 at 20:34
-
1$\begingroup$ How about Mill's formula? en.wikipedia.org/wiki/Mills%27_constant $\endgroup$– OviMay 27, 2016 at 21:25
-
$\begingroup$ @Ovi While interesting, that doesn't give the $n$th prime; it gives only a particular subsequence of primes (where moreover knowing anything about the constant or even the first generated prime depends on the Riemann hypothesis, and even then it seems the constant is calculated from the primes, rather than the primes being generated from the constant: the value of the constant is thus a "summary" which encodes the primes found.) $\endgroup$ May 28, 2016 at 1:48
$\begingroup$
$\endgroup$
8
Far better than sieving in the large range ShreevatsaR suggested (which, for the 10¹⁵th prime, has 10¹⁵ members and takes about 33 TB to store in compact form), take a good first guess like Riemann's R and use one of the advanced methods of computing pi(x) for that first guess. (If this is far off for some reason—it shouldn't be—estimate the distance to the proper point and calculate a new guess from there.) At this point, you can sieve the small distance, perhaps just 10⁸ or 10⁹, to the desired number.
This is about 100,000 times faster for numbers around the size I indicated. Even for numbers as small as 10 to 12 digits, this is faster if you don't have a precomputed table large enough to contain your answer.
-
$\begingroup$ Thanks. I've updated my answer to not recommend sieving. $\endgroup$ Sep 9, 2010 at 7:30
-
3$\begingroup$ @ShreevatsaR: Don't get me wrong -- your answer is far better than the naive method of stepping through numbers and testing them! I was just suggesting an improvement. :) $\endgroup$– CharlesSep 9, 2010 at 18:55
-
$\begingroup$ "At this point you can sieve the small distance, perhaps just 10^8 or 10^9, to the desired number." How would you recognize this number? $\endgroup$– LiviuJan 17, 2016 at 15:00
-
4$\begingroup$ @Charles "your guess is very far off" ... how can I know that a prime is the prime I am searching for ... without counting all the primes until it? $\endgroup$– LiviuJan 22, 2016 at 14:51
-
3$\begingroup$ @Liviu: Suppose you have a fast test for (1) whether a number is prime or not and (2) a fast test to find the number of primes less than or equal to a given number. If I claim that a number $p$ is the $n$th prime, all you have to do is check that $p$ is prime using (1) and check that $\pi(p)=n$ by (2). (1) is relatively easy, but (2) is hard. See mathworld.wolfram.com/PrimeCountingFunction.html for an overview on the latter. There are two classes of fast approaches to (2), analytic and combinatorial, and they are roughly tied at record sizes (at smaller sizes combinatorial is better). $\endgroup$– CharlesJan 22, 2016 at 22:45
$\begingroup$
$\endgroup$
3
There are formulas on Wikipedia, though they are messy. No polynomial $p(x)$ can output the $n$th prime for all $n$, as is explained in the first section of the article.
There is, however, a polynomial in 26 variables whose nonnegative values are precisely the primes. (This is fairly useless as far as computation is concerned.) This comes from the fact that the property of being a prime is decidable, and the theorem of Matiyasevich.
answered Jul 30, 2010 at 21:26
-
$\begingroup$ Note that this 26-variable polynomial isn't well suited to generate primes, as most of its codomain is negative. $\endgroup$– stevenvhAug 7, 2010 at 17:39
-
1$\begingroup$ I remember it was presented to us in the elementary course of number theory, and I think the teacher said that after much work they managed to reduce it to 22 variables. $\endgroup$– Asaf Karagila ♦Sep 11, 2010 at 17:59
-
14$\begingroup$ This 26-variable polynomial still gives me the creeps. I find it very strange indeed. $\endgroup$– SputnikJun 7, 2011 at 22:45
$\begingroup$
$\endgroup$
No such formula is known, but there are a few that give impressive results. A famous one is Euler's: $$P(n) = n^2 − n + 41$$ Which yields a prime for every natural number lower than $41$, though not necessarily the $n$th prime.
See more here.
