Misplaced Pages

Talk:Formula for primes: Difference between revisions

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 14:42, 24 December 2012 editJayme (talk | contribs)388 edits Formula for the nth prime← Previous edit Revision as of 16:17, 7 April 2013 edit undoL2j2 (talk | contribs)115 edits →Formula for the nth primeNext edit →
Line 269: Line 269:
==Formula for the nth prime== ==Formula for the nth prime==
In ] it is written: "here's a forula for the nth prime: <math>p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor \ } \right\rfloor^{1 \over n} \right\rfloor.</math>" ] (]) 14:42, 24 December 2012 (UTC) In ] it is written: "here's a forula for the nth prime: <math>p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor \ } \right\rfloor^{1 \over n} \right\rfloor.</math>" ] (]) 14:42, 24 December 2012 (UTC)

==old version ==

In ], a '''formula for primes''' is a formula generating the ]s, exactly and without exception. No such formula which is easily ] is presently known. A number of constraints are known: what such a "formula" can and cannot be.

==Prime formulas and polynomial functions==

It is known that no non-] ] function ''P''(''n'') with integer coefficients exists that evaluates to a ] for all integers ''n''. The proof is as follows: Suppose such a polynomial existed. Then ''P''(1) would evaluate to a prime ''p'', so <math>P(1) \equiv 0 \pmod p</math>. But for any ''k'', <math>P(1+kp) \equiv 0 \pmod p</math> also, so <math>P(1+kp)</math> cannot also be prime (as it would be divisible by ''p'') unless it were ''p'' itself, but the only way <math>P(1+kp) = P(1)</math> for all ''k'' is if the polynomial function is constant.

The same reasoning shows an even stronger result: no non-constant polynomial function ''P''(''n'') exists that evaluates to a prime number for ] integers ''n''.

] first noticed (in 1772) that the ]
:''P''(''n'') = ''n''<sup>2</sup> - ''n'' + 41
is prime for all ]s less than 41. The primes for ''n'' = 1, 2, 3... are 41, 43, 47, 53, 61, 71... The differences between the terms are 2, 4, 6, 8, 10... For ''n'' = 41, it produces a square number, 1681, which is equal to 41×41, the smallest ] for this formula. If 41 divides ''n'' it divides ''P(n)'' too. The phenomenon is related to the ], which is also implicitly quadratic, and the ];
this polynomial is related to the ] <math>163=4\cdot 41-1</math>, and there are analogous polynomials for <math>p=2, 3, 5, 11, \text{ and } 17</math>, corresponding to other Heegner numbers.

It is known, based on ], that linear polynomial functions <math>L(n) = an + b</math> produce infinitely many primes as long as ''a'' and ''b'' are ] (though no such function will assume prime values for all values of ''n''). Moreover, the ] says that for any ''k'' there exists a pair of ''a'' and ''b'' with the property that <math>L(n) = an+b</math> is prime for any ''n'' from 0 to ''k''&nbsp;−&nbsp;1. However, the best known result of such type is for ''k'' = 26:
:43142746595714191 + 5283234035979900''n'' is prime for all ''n'' from 0 to 25 {{harv|Andersen|2010}}.

It is not even known whether there exists a univariate polynomial of degree at least 2 that assumes an infinite number of values that are prime; see ].

==Formula based on a system of Diophantine equations==

A system of 14 ]s in 26 variables can be used to obtain a Diophantine representation of the set of all primes. {{Harvtxt|Jones|Sato|Wada|Wiens|1976}} proved that a given number ''k''&nbsp;+&nbsp;2 is prime ] the following system of 14 Diophantine equations has a solution in the ]s:

: α<sub>0</sub> = <math> wz + h + j - q </math> = 0

: α<sub>1</sub> = <math> (gk + 2g + k + 1)(h + j) + h - z </math> = 0

: α<sub>2</sub> = <math> 16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2 </math> = 0

: α<sub>3</sub> = <math> 2n + p + q + z - e </math> = 0

: α<sub>4</sub> = <math> e^3(e + 2)(a + 1)^2 + 1 - o^2 </math> = 0

: α<sub>5</sub> = <math> (a^2 - 1)y^2 + 1 - x^2 </math> = 0

: α<sub>6</sub> = <math> 16r^2y^4(a^2 - 1) + 1 - u^2 </math> = 0

: α<sub>7</sub> = <math> n + l + v - y </math> = 0

: α<sub>8</sub> = <math> (a^2 - 1)l^2 + 1 - m^2 </math> = 0

: α<sub>9</sub> = <math> ai + k + 1 - l - i </math> = 0

: α<sub>10</sub> = <math> ((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2 </math> = 0

: α<sub>11</sub> = <math> p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m </math> = 0

: α<sub>12</sub> = <math> q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x </math> = 0

: α<sub>13</sub> = <math> z + pl(a - p) + t(2ap - p^2 - 1) - pm </math> = 0

The 14 equations α<sub>0</sub>, …, α<sub>13</sub> can be used to produce a prime-generating polynomial inequality in 26 variables:

:<math> (k+2)(1-\alpha_0^2-\alpha_1^2-\cdots-\alpha_{13}^2) > 0 </math>

i.e.:

:<math> (k+2) (1 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2 - </math>
:<math> ^2) </math>
:<math> > 0 </math>

is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables ''a'', ''b'', …, ''z'' range over the nonnegative integers.

A general theorem of ] says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables. Hence, there is a prime-generating polynomial as above with only 10 variables. However, its degree is large (in the order of 10<sup>45</sup>). On the other hand, there also exists such a set of equations of degree only 4, but in 58 variables.{{harv|Jones|1982}}

==Formulas using the floor function==

Using the ] <math>\lfloor x\rfloor</math> (defined to be the largest integer less than or equal to the ] ''x''), one can construct several formulas that take only prime numbers as values for all positive integers ''n''.

===Mills's formula===

The first such formula known was established in 1947 by ], who proved that there exists a ] ''A'' such that

:<math>\lfloor A^{3^{n}}\;\rfloor</math>

is a prime number for all positive integers ''n''. If the ] is true, then the smallest such ''A'' has a value of around 1.3063... and is known as ]. This formula has no practical value, because very little is known about the constant (not even whether it is ]), and there is no known way of calculating the constant without finding primes in the first place.

===Converting the sieve of Eratosthenes to prime number formulas===
There is another, quite different formula discovered by Sebastián Martín-Ruiz {{harv|Rivera|n.d.}} and proved with ] {{harv|Martin-Ruiz|Sondow|2002}}:
:<math>\pi(k) = k - 1 + \sum_{j=1}^k \left\lfloor {2 \over j} \left(1 + \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor </math>

Note the following equalities:

:<math>\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor = \begin{cases}
1 & s \text{ divides } j \\
0 & s \text{ does not divide } j
\end{cases} </math>

:<math>2\sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) = \text{number of divisors of } j </math>

:<math>\left\lfloor {-1 \over j} \sum_{s=2}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right)\right\rfloor=\begin{cases}
0 & j \text{ is prime} \\
-1 & j \text{ is composite}
\end{cases}</math>

:<math>\operatorname{IsPrime}(j)=1+\left\lfloor {-1 \over j} \sum_{s=2}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) \right\rfloor=\begin{cases}
1 & j \text{ is prime} \\
0 & j \text{ is composite}
\end{cases}</math>

:<math>\pi(k) =\sum_{j=2}^k \operatorname{IsPrime}(j),</math>

where <math>\pi(k)</math> is the ].

===Converting primality tests to prime number formulas===

Any ] can be used as the basis for a prime number formula. In effect, a test for the primality of ''n'' is a computation of the function IsPrime(''n''), defined by:
:<math>\operatorname{IsPrime}(n) =
\begin{cases}
1 & n \text{ prime} \\
0 & n \text{ composite}
\end{cases}
</math>
If the primality test is given by a condition on some formula involving <math>n,</math> then that formula gives a formula for IsPrime(''n''). Using a product,
:<math>\prod_{k=2}^{n} \prod_{l=2}^{n} (n-kl) = 0\text{ if and only if n is not a prime (and integer more than 1)}</math>
For a prime <math>n \ge 2</math>,the product above is not 0. So,
:<math>\operatorname{IsPrime}(n) =
\operatorname{abs} \left( \operatorname{sgn} \left( \prod_{k=2}^{n} \prod_{l=2}^{n} (n-kl)\right) \right)</math>
where n is more than 1. However, the product is very large or very small where n is a prime so
:<math>\operatorname{IsPrime}(n) =
\operatorname{abs}\left( \prod_{k=2}^{n} \prod_{l=2}^{n} \operatorname{sgn} (n-kl)\right).</math>
Moreover, we need not calculate product up to k=l=n.
:<math>\operatorname{IsPrime}(n) =
\operatorname{abs}\left( \prod_{k=2}^{\lfloor\frac{n}{2}\rfloor } \prod_{l=2}^{\operatorname{min}(k,\lfloor\frac{n}{k}\rfloor)} \operatorname{sgn} (n-kl)\right).</math>
] states that ''n'' is prime ] it divides <math>(n - 1)! + 1.</math> To express this by an explicit formula, two intermediate functions are introduced:
:<math>r(n) = \frac{(n - 1)! + 1}{n},</math>
:<math>\operatorname{IsInteger}(x) =
\begin{cases}
1 & x \text{ is an integer} \\
0 & x \text{ is not an integer}
\end{cases}
</math>
Then Wilson's theorem says that
:<math>\operatorname{IsPrime}(n) = \operatorname{IsInteger}\bigl(r(n)\bigr).</math>
This can be further specified by an explicit formula for IsInteger(''x''). Some options are:
:<math>\operatorname{IsInteger}(x) = \lfloor x\rfloor + \lfloor -x \rfloor + 1</math>
:<math>\operatorname{IsInteger}(x) = \left\lfloor \frac{\lfloor x \rfloor}{x} \right\rfloor</math>
:<math>\operatorname{IsInteger}(x) = \lfloor \cos^2(\pi x) \rfloor</math> : formula by C. P. Willans {{harv|Bowyer|n.d.}}
Then, for example, taking the first option gives a formula for IsPrime(''n'') using Wilson's theorem:
:<math>\operatorname{IsPrime}(n) =
\left\lfloor \frac{(n - 1)! + 1}{n} \right\rfloor + \left\lfloor -\frac{(n - 1)! + 1}{n} \right\rfloor + 1
</math>
Not using the function IsInteger,
:<math>\operatorname{IsPrime}(n) = \operatorname{abs}\left(\prod_{k=1}^{(n-1)!} \operatorname{sgn}((n-1)!+1-kn)\right).</math>
Once IsPrime(''n'') can be computed, the ] <math>\pi(n)</math> can as well, since by definition
:<math>\pi(n) = \text{number of primes less than or equal to } n = \sum_{k = 1}^n \operatorname{IsPrime}(k).</math>
<math>\pi(n)</math> can then compute a function testing whether a given integer ''n'' is the ''m''<sup>th</sup> prime:
:<math>\operatorname{IsNthPrime}(n,m) =
\operatorname{IsPrime}(n) * \operatorname{IsZero}(\pi(n) - m) =
\begin{cases}
1 & n \text{ is the } m^\text{th} \text{ prime} \\
0 & \text{otherwise}
\end{cases}
</math>
The function IsZero(''x'') can likewise be expressed by a formula:
:<math>\operatorname{IsZero}(n) = \left\lfloor {1 \over {1+|n|}}\right\rfloor,</math>

Finally, the IsNthPrime(<math>n,m</math>) function can be used to produce a formula for the ''n''<sup>th</sup> prime:
:<math>p_n = \sum_{m = 1}^{2^n} m * \operatorname{IsNthPrime}(m,n).</math>
The upper bound 2<sup>''n''</sup> comes from ], which implies that there is a sequence of primes
:<math>2 = p_1 < p_2 < \dots < p_n,</math> where <math>p_{i + 1} < 2 p_i. </math> Thus, <math>p_n < 2^n.</math>
Substituting the formulas above and applying Wilson's theorem gives a formula for <math>p_n</math> involving the arithmetic operations and the floor function. Other such formulas are:
:<math>p_n = 1 + \sum_{k=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \pi(k) } \right\rfloor^{1 \over n} \right\rfloor.</math>
in which the following equality is important:
:<math>\left\lfloor \left\lfloor { n \over 1 + \pi(k) } \right\rfloor^{1 \over n} \right\rfloor={\begin{cases}
1, & \text{if } \pi(k) \le n-1 \\
0, & \text{if } \pi(k) > n-1
\end{cases}} </math>
and
:<math>p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\pi(k) \over n} \right\rfloor\right)
</math>
by Sebastián Martín-Ruiz and proved with Jonathan Sondow {{harv|Martin-Ruiz|Sondow|2002}}. A similar formula for <math>p_n</math> was given earlier by Stephen Regimbal {{harv|Regimbal|1975}}.

==Recurrence relation==
Another prime generator is defined by the ]
:<math> a_n = a_{n-1} + \operatorname{gcd}(n,a_{n-1}), \quad a_1 = 7, </math>
where gcd(''x'', ''y'') denotes the ] of ''x'' and ''y''. The sequence of differences ''a''<sub>''n'' + 1</sub> − ''a<sub>n</sub>'' starts with 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 {{OEIS|id=A132199}}. {{harvtxt|Rowland|2008}} proved that this sequence contains only ones and prime numbers.

==See also==
* ]

==References==
<div class="references-small">
* {{citation | first1=Jens Kruse | last1=Andersen | year=2010 | title=Primes in Arithmetic Progression Records | url=http://users.cybercity.dk/~dsl522332/math/aprecords.htm | accessdate=2010-04-13 }}.
* {{citation | first1=Adrian | last1=Bowyer | year=n.d. | pages=11761 | title=Formulae for Primes | journal=Eprint arXiv:math/0611761 | url=http://people.bath.ac.uk/ensab/Primes/ | accessdate=2008-07-09 | bibcode=2006math.....11761F |arxiv = math/0611761 }}.
* {{citation | first1=James P. | last1=Jones | first2=Daihachiro | last2=Sato | first3=Hideo | last3=Wada | first4=Douglas | last4=Wiens | author4-link=Douglas Wiens | url = http://mathdl.maa.org/mathDL/?pa=content&sa=viewDocument&nodeId=2967&pf=1 | year=1976 | title=Diophantine representation of the set of prime numbers | journal=] | volume=83 | pages=449–464 | doi=10.2307/2318339 | jstor=2318339 | issue=6 | publisher=Mathematical Association of America}}.
* {{citation | doi=10.2307/2273588 | first=James P. | last=Jones | year=1982 | title=Universal diophantine equation | journal=Journal of Symbolic Logic | volume=47 | issue=3 | pages=549–571}}.
* {{cite arxiv | first1=Sebastian | last1=Martin-Ruiz | first2=Jonathan | last2=Sondow | year=2002 | title=Formulas for ''π''(''n'') and the ''n''th prime | eprint=math/0210312| }}.
* {{Citation | doi=10.2307/2690354 | last1=Regimbal | first1=Stephen | title=An explicit Formula for the k-th prime number | jstor=2690354 | year=1975 | journal=Mathematics Magazine | volume=48 | pages=230–232 | issue=4 | publisher=Mathematical Association of America}}.
* {{citation | first1=Carlos | last1=Rivera | year=n.d. | title=Problem 38. Sebastián Martín Ruiz- Prime formulas | url=http://www.primepuzzles.net/problems/prob_038.htm | accessdate=2008-07-09 }}.
* {{Citation | last1=Rowland | first1=Eric S. | title=A Natural Prime-Generating Recurrence | url=http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html | year=2008 | journal=Journal of Integer Sequences | volume=11 | pages=08.2.8 | bibcode=2008JIntS..11...28R|arxiv = 0710.3217 }}.
* {{citation | last = Matiyasevich | first = Yuri V. | authorlink = Yuri Matiyasevich | title = Formulas for Prime Numbers | journal = Eprint arXiv:math/0611761 | pages = 11761 | year = 2006 | bibcode = 2006math.....11761F|arxiv = math/0611761 }} ({{citation | first = Serge | last = Tabachnikov | title = Kvant selecta: algebra and analysis | volume = 1 | publisher = AMS Bookstore | isbn = 978-0-8218-1915-9}}, ).
</div>
{{reflist}}

==External links==
* {{MathWorld|urlname=PrimeFormulas|title=Prime Formulas}}
* {{MathWorld|urlname=Prime-GeneratingPolynomial|title=Prime-Generating Polynomial}}
* {{MathWorld|urlname=MillsConstant|title=Mill's Constant}}
*A Venugopalan. ''Formula for primes, twinprimes, number of primes and number of twinprimes''. Proceedings of the Indian Academy of Sciences—Mathematical Sciences, Vol. 92, No 1, September 1983, pp.&nbsp;49–52. Page , , , , .

{{Prime number classes}}

]

Revision as of 16:17, 7 April 2013

Formulas that frequently produce primes

Do you know of any other formulas that produce primes so frequently?? Name some. User:66.32.255.166

Try Prime number and the section "Formulas yielding prime numbers" which has some. It is rather better than this page, so I will copy the content from there to here. --Henrygb 00:41, 7 May 2004 (UTC)

Reversion of changes by an anon

I've reverted all the changes by this anon guy. He keeps adding info to articles when it's been moved from one article to another, and he also has been deleting/altering comments on talk pages. CryptoDerk 03:14, Mar 5, 2005 (UTC)

Removal of formula

I've removed this formula as it clearly doesn't do what it is claimed to, but I cannot find a reference to fix it (the lack of a reference is itself a problem). I do hope someone can supply the corrected version Robma 11:17, 14 May 2006 (UTC)

It doesn't? It seemed to when I tried it... — vijay 18:14, 14 May 2006 (UTC)

Using MathCad it started producing composites around the n = 27 mark. But I suspect this may be due to rounding error. Either way, I still think we need a reference for this formula (I for one would be v interested to learn more about it; it's an unusually neat result for this field). Robma 21:06, 14 May 2006 (UTC)

Hrm. Around that range (excluding the 2s) I get
  • n=22 => 23
  • n=28 => 29
  • n=30 => 31
  • n=36 => 37
  • n=40 => 41
I used Java ('cause it's what I have), and of course, I used ints at first, which led to an overflow and negative output. Switching to BigInteger did the trick :-). A reference would be good, though. I put a note on the contributing editor's talk page. — vijay 22:24, 14 May 2006 (UTC)
Great stuff; thanks for confirming that. I'll get in touch with some people about getting a ref for this formula, and also the one queried below (which again is unfamiliar to me too).Robma 07:29, 16 May 2006 (UTC)

Robma, please specify which formula you are removing from the article instead of just referring to it on the talk page as "this" formula so that editors don't have to hunt through the page's history (which is easy now, but won't be so easy months in the future). Thanks! Anyway, the formula under discussion here, for the benefit of people reading this talk page, is:

f ( n ) = 2 + [ ( 2 ( n ! ) ) mod ⁡ ( n + 1 ) ] . {\displaystyle f(n)=2+.}

I've restored it, since it seems from the above discussion and that the formula is correct, even if we still are missing a citation. The formula was originally added by User:LC to the prime number article () and then moved to this article by User:Henrygb. —Lowellian (reply) 04:46, 25 May 2006 (UTC)

Ah, ha! With a little help from a friend, here is the proof, which is rather trivial:
First, consider the case where n is one less than a prime, that is, when n = p − 1 {\displaystyle n=p-1} . This is equivalent to saying that the modulus n + 1 {\displaystyle n+1} is prime. Then:
f ( n ) = 2 + [ 2 n ! mod ⁡ ( n + 1 ) ] = 2 + [ 2 ( p − 1 ) ! mod ⁡ ( ( p − 1 ) + 1 ) ] {\displaystyle f(n)=2+=2+}
Applying Wilson's theorem, we get:
f ( n ) = 2 + [ 2 ( − 1 ) mod p ] = 2 + ( − 2 mod p ) = 2 + ( p − 2 ) = p {\displaystyle f(n)=2+=2+(-2\,\operatorname {mod} \,p)=2+(p-2)=p}
So clearly, when the modulus n + 1 {\displaystyle n+1} is a prime p, f ( n ) = p {\displaystyle f(n)=p} , so when n + 1 {\displaystyle n+1} is prime, f ( n ) {\displaystyle f(n)} ranges over all the primes.
Now, we still have to prove that when n + 1 {\displaystyle n+1} is not prime, we get f ( n ) = 2 {\displaystyle f(n)=2} . To prove this, all we need to do is show that n ! mod ⁡ ( n + 1 ) ≡ 0 {\displaystyle n!\,\operatorname {mod} (n+1)\equiv 0} , since then that term drops out, leaving only the 2. We proceed to do this:
If n + 1 {\displaystyle n+1} is not prime, then we can write n + 1 = p k {\displaystyle n+1=pk} , where p is the smallest prime that divides n + 1 {\displaystyle n+1} . Clearly, since p and k are both factors of n + 1 {\displaystyle n+1} , we have p < n + 1 {\displaystyle p<n+1} and k < n + 1 {\displaystyle k<n+1} . Unless p = k {\displaystyle p=k} , both p and k are distinct factors of the expansion n ! = n × ( n − 1 ) × ( n − 2 ) × . . . × 1 {\displaystyle n!=n\times (n-1)\times (n-2)\times ...\times 1} , implying that n ! m o d ( p k ) ≡ n ! m o d ( n + 1 ) ≡ 0 {\displaystyle n!\,{mod}\,(pk)\equiv n!\,{mod}\,(n+1)\equiv 0} .
Now, let's take the final case, where n + 1 = p k {\displaystyle n+1=pk} and p = k {\displaystyle p=k} , that is, wherein n + 1 = p 2 {\displaystyle n+1=p^{2}} . We know p < n + 1 {\displaystyle p<n+1} , since p is the square root of n + 1 {\displaystyle n+1} , and 2 p < n + 1 {\displaystyle 2p<n+1} , since for all integers m ≥ 3 {\displaystyle m\geq 3} , 2 m < m 2 {\displaystyle 2m<m^{2}} . Therefore, the expansion n ! = n × ( n − 1 ) × ( n − 2 ) × . . . × 1 {\displaystyle n!=n\times (n-1)\times (n-2)\times ...\times 1} contains both 2p and p, so p 2 | n ! {\displaystyle p^{2}|n!} and n ! m o d ( p 2 ) ≡ n ! m o d ( n + 1 ) ≡ 0 {\displaystyle n!\,{mod}\,(p^{2})\equiv n!\,{mod}\,(n+1)\equiv 0} . QED.
—Lowellian (reply) 04:19, 26 May 2006 (UTC)

Correct formula

I have a doubt with the formula for n-th prime, i have never seen it demonstrated i mean: --Karl-H 20:35, 15 May 2006 (UTC)


p n = 1 + ∑ m = 1 2 n ⌊ ⌊ n 1 + π ( m ) ⌋ 1 n ⌋ . {\displaystyle p_{n}=1+\sum _{m=1}^{2^{n}}\left\lfloor \left\lfloor {n \over 1+\pi (m)}\right\rfloor ^{1 \over n}\right\rfloor .}

Venugopalan Atiyolil's formula for the (n+1)th Prime

"In the Proceedings of the Indian Academy of Sciences(Math. Sci.), Vol.92, No.1,September 1983 pp 49-52, an explicit formula for the (n+1)th Prime which is the same as nth Prime as n could be substituted for n+1 for a given integer. In other words, if one wants to find the 6th Prime Number, then the integer n=5. The paper also gives a formula for the (n+1)th Twin prime which is the same as the nth Twin Prime. Further, the paper gives formulae for number of Primes and Twin Primes less than any given Prime. The proof is written in a cumbersome format to avoid plagiarism and therefore it is difficult to follow. The following are the pages of the paper. http://www.ias.ac.in/jarch/mathsci/92/00000050.pdf http://www.ias.ac.in/jarch/mathsci/92/00000051.pdf http://www.ias.ac.in/jarch/mathsci/92/00000052.pdf http://www.ias.ac.in/jarch/mathsci/92/00000053.pdf http://www.ias.ac.in/jarch/mathsci/93/00000068.pdf"

This paragraph is hard to understand. Here is my suggestion, but I haven't implemented it because I am uncertain that my reformulation replicates the meaning of the original.

"In the Proceedings of the Indian Academy of Sciences(Math. Sci.), Vol.92, No.1, September 1983 pp 49-52, an explicit formula for the nth prime number is given. The paper also gives a formula for the nth twin prime. Further, the paper gives formulae for the number of primes and twin primes less than any given prime. The proof is written in a cumbersome format to avoid plagiarism and therefore it is difficult to follow. The following are the pages of the paper. http://www.ias.ac.in/jarch/mathsci/92/00000050.pdf http://www.ias.ac.in/jarch/mathsci/92/00000051.pdf http://www.ias.ac.in/jarch/mathsci/92/00000052.pdf http://www.ias.ac.in/jarch/mathsci/92/00000053.pdf http://www.ias.ac.in/jarch/mathsci/93/00000068.pdf"--Dougall 07:47, 14 July 2006 (UTC)

One good thing of these formulae is that the paper gives a formula for the number of twin primes. The twin prime conjecture is still unsolved ! All formulae are very correct with consideration to errata published (00000068.pdf). — Preceding unsigned comment added by 72.87.101.104 (talk) 01:44, 29 June 2011 (UTC)

The reason why some people could not understand the above paper is becasue they don't interpret as INTEGRAL PART in step 16 of the page 51 of the paper to get the (n+1)th prime.

Can someone elaborate or simplyfy proof of this formulae for Prime Numbers, Twin Primes, Number of Primes and number of Twin Primes as the formula is correct if you read the errata (00000068.pdf), later published. It seems there was a printing error which was later corrected. Proceedings of the Indian Academy of Sciences only publishes papers after three referees(mathematicians) who peruse the contents as correct to be published. Sometimes there could be printing errors. The sign is denoted for integral part -not just a bracket!

After reading all these criticisms on a mathematically correct issue,which was refereed by three mathematicians, it seems only reasonable that the Author chose to publish the proof in an obscure way to aviod stealth by greed. Be positive in thinking and you would only indulge yourself into elimination of myth manufactured by ignorance. No wonder people quit research as it is sometime non-rewarding and a subject of negetive criticism. The papers stands still with no progress even after all these years when the Author was just about to prove or disprove twin prime conjecture. Learn a lesson from it.

—Preceding unsigned comment added by 64.223.54.183 (talk)

Concerning the paper of Venu Atiyolil

I am going to note that the mentioned formula has a running time of at least seeking out the next prime and trial dividing in any practical case.

—Preceding unsigned comment added by 69.254.220.41 (talk • contribs) 21:26, 4 October 2006

It is the first explicit formula for the nth Prime. Nothing to do with running time. It could be simplified if done enough research. —Preceding unsigned comment added by 74.97.4.93 (talk) 01:21, 23 December 2010 (UTC)

Error in Formula based on a system of Diophantine equations

The given prime-generating polynomial seems to be wrong. The right formula should be: (K+2)(1-α1-α2-...-α14). 89.138.48.98 15:30, 9 April 2007 (UTC)

You're absolutely right. Thanks a lot! -- Jitse Niesen (talk) 01:47, 10 April 2007 (UTC)
Yet neither of you corrected it, anyway it's done now. Smithers888 (talk) 22:36, 13 June 2008 (UTC)

Polynomial formulaes --> editing a bit_editing_a_bit">

At the moment it is written: "A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables. Hence, there is a prime-generating polynomial as above with only 10 variables. However, its degree is large (in the order of 1045)."

This can be misunderstood by reader like this: "the degree of any prime-generating polynomial with 10 variables is at least 10^45" --> however, only the currently known method of getting such polynomial require degree 10^45; there is a chance that someone will find the prime-generating polynomial with 10 variables using completely other method and get much smaller value. As far as I understand the only 2 known results about prime-generating polynomials are that if such polynomial has A variables and B is its degree, then A>1 and B>1 (and no better estimations are known), so, there is a chance that some polynomial with 2 variables of degree 2 is prime-generating.

If someone can rewrite the text a bit to exclude such misunderstanding, this will be great (my English is not very good as you see). Thanks.

—Preceding unsigned comment added by 217.150.50.194 (talk • contribs) 10:40, 25 May 2007

Moved formula from article

I have reverted the following addition to the article. My edit summary "revert latest edit. Very complicated formula with no explanation. Sums 2^n numbers to find nth prime. Must be among the slowest ever if it works" PrimeHunter 01:03, 8 August 2007 (UTC)

Formula elaborated by Lainé Jean Lhermite Junior

P n = ∑ i = 1 2 n h ( i ) {\displaystyle P_{n}=\sum _{i=1}^{2^{n}}h(i)}

visit : http://www.institutionscle.nombrespremiers.net


P n = ∑ i = 1 2 n ( ⌊ 1 + ∑ m = 1 i ( 1 − ⌊ ⌊ ( m ! ) 2 m 3 ⌋ ( m ! ) 2 m 3 ⌋ ) n + 1 ⌋ × ⌊ n + 1 1 + ∑ m = 1 i ( 1 − ⌊ ⌊ ( m ! ) 2 m 3 ⌋ ( m ! ) 2 m 3 ⌋ ) ⌋ × i × ( 1 − ⌊ ⌊ ( ( i ! ) 2 i 3 ⌋ ( i ! ) 2 i 3 ⌋ ) ) {\displaystyle P_{n}=\sum _{i=1}^{2^{n}}\left(\left\lfloor {\frac {1+\sum _{m=1}^{i}{\left(1-\left\lfloor {\frac {\left\lfloor {\frac {\left(m!\right)^{2}}{m^{3}}}\right\rfloor }{\frac {\left(m!\right)^{2}}{m^{3}}}}\right\rfloor \right)}}{n+1}}\right\rfloor \times {\left\lfloor {\frac {n+1}{1+\sum _{m=1}^{i}{\left(1-\left\lfloor {\frac {\left\lfloor {\frac {\left(m!\right)^{2}}{m^{3}}}\right\rfloor }{\frac {\left(m!\right)^{2}}{m^{3}}}}\right\rfloor \right)}}}\right\rfloor }\times {i}\times {\left({1-\left\lfloor {\frac {\left\lfloor ({\frac {\left(i!\right)^{2}}{i^{3}}}\right\rfloor }{\frac {\left(i!\right)^{2}}{i^{3}}}}\right\rfloor }\right)}\right)}


Polynomial equations

Hank Harrell has done work in this area He claims the following produces 12 fold the # primes over what is expected on average (using P#=151*149*139*...2,c=73033421, x={1,1000}):

candidate = P#*x^2-P#*x + C, where P# is a primorial and C is a positive integer

Essentially it is a "prime candidate -generating" equation akin to the older classics but yielding much larger primes--Billymac00 (talk) 17:03, 18 February 2008 (UTC)

Goldbach's

in effect, is a simple (iterative) prime "formula" always returning 2 primes each >=5 from each input pair described as:

starting with 2 integers (same parity, at least 1 not prime,>=6),

(N1,N2) via (N1-d,N2+d) will yield 2 primes < (N1+N2)
where max d = max(N1,N2)-5

An example is (39,25) which generates (4) pairs (max d=34)

(23,41), (17,47), (11,53), (5,59)


Similarly, (32,32) generates the same (4) pairs as 32+32 =39+25 (identical sums)
It generates "varied" bounded primes --Billymac00 (talk) 22:17, 6 March 2008 (UTC)

Formula based on Wilson's theorem

I removed the following text from the section "Other formulas":

This formula is wrong and no longer is able to creat many of prime numbers, i.e. i have examined it for n = 18 and it's result was not correct! This formula has generate 2 for every n greater than 19. And for n = 18 the result is 18 that is obvious it is'nt a prime number!!
—Preceding unsigned comment added by Threepehr (talk • contribs) 04:39, 12 May 2008

I tried it out for n = 18, and I got 19, just as the theory predicts. -- Jitse Niesen (talk) 11:38, 12 May 2008 (UTC)

Yes, the formula is correct. The IP must have evaluated it incorrectly. PrimeHunter (talk) 18:00, 12 May 2008 (UTC)
Can people who don't know much mathematics not edit maths articles please. The Wilson formula is pretty trivially correct and well-known —Preceding unsigned comment added by 94.172.196.23 (talk) 12:15, 19 July 2009 (UTC)

Misplaced Pages's Expert Peer Review process (or lack of such) for Science related articles

Hi - I posted the section with the same name on my talk page. Could you take part in discussion ? Thanks ARP Apovolot (talk) 21:28, 25 October 2008 (UTC)

Small arithmetic change

I'm sure that

IsPrime ⁡ ( n ) = ⌊ ( n − 1 ) ! + 1 n ⌋ + ⌊ − ( n − 1 ) ! + 1 n ⌋ + 1 {\displaystyle \operatorname {IsPrime} (n)=\left\lfloor {\frac {(n-1)!+1}{n}}\right\rfloor +\left\lfloor -{\frac {(n-1)!+1}{n}}\right\rfloor +1}

...is exactly the same as...

IsPrime ⁡ ( n ) = 2 ⌊ − ( n − 1 ) ! + 1 n ⌋ + 1 {\displaystyle \operatorname {IsPrime} (n)=2\left\lfloor -{\frac {(n-1)!+1}{n}}\right\rfloor +1}

No?
 Ignore this, I missed the negative sign. 58.7.8.182 (talk) 16:05, 30 June 2009 (UTC)

MILLS formula is WRONG!

PROGRAM ImbalzanoG; begin REPEAT write("MILLS formula is WRONG!") until TRUE end. (*All the best!*) —Preceding unsigned comment added by Imbalzanog (talk • contribs) 13:33, 29 August 2009 (UTC)

I guess you are User:Jmbalzan who made this edit. Please don't make edits about the same thing using different accounts. See Misplaced Pages:Sock puppetry. Mills' constant lists reliable sources for the formula and the statement that it's unknown whether Mills' constant is rational. Misplaced Pages does not allow original research. PrimeHunter (talk) 16:08, 29 August 2009 (UTC)


OK! <jmbalzan> = <user:imbalzanog> but the 'MILLS formula is wrong! In fact (IF A=1.30637788386308069046) for n=0, 1, 2, .., 4 one obtain the "prime numbers".. 1, 1, 2, .., 1361, but for n=3 one obtain 8 ..NOT 11, like from the sequence 1, 1, 2, 11, 1361, 2521008887.. or the Riemann hypothesis is wrong?! All the best for this! Prof. Giovanni Imbalzano, ThanX. —Preceding unsigned comment added by Imbalzanog (talk • contribs) 19:50, 29 August 2009 (UTC)

Your calculation for n=3 is wrong, and the primes start at n=1, not at n=0. For n = 1, 2, 3, 4, ...
floor(A) = 2, 11, 1361, 2521008887... (sequence A051254 in the OEIS)
For n=3 it is floor(A) = floor(A) = floor(11.082031) = 11. No integer n gives the value 8. PrimeHunter (talk) 20:14, 29 August 2009 (UTC)

Sorry! My (PASCAL and) FORTRAN program done: A^(n^3)= A(2^3)=8.483021265734882348686267276902336962502905672556765306326251816065644520340083810648493349954739074, =>FLOOR=8 NOT 11 but I use A=1.30637788386308069046 and "real or complex number calculations with 100-significant-figure precision. " ..AND for n=3: 1361.000001079726460999192860124432416917474694599497777199482905339934552915037249561521962884051614 Evident! The formula is A^(3^n) NOT A^(n^3)..! PARDON, but I search of verifies again ! FOR n=4 FORTRAN done: A^(3^n)= 2521008886.999999998653456843300060421152569980618097269190530906867869731446814744897933120185555674, FLOOR=2521008886 NOT prime, CEIL=2521008887... —Preceding unsigned comment added by Imbalzanog (talk • contribs) 20:52, 29 August 2009 (UTC) ..AND finally FOR n=5: A^(3^n)= 16022236204009818106157512334.85693084207614172497541238587106571181797337053375889904228588259040492 FLOOR=16022236204009818106157512334, CEIL=16022236204009818106157512335, both NON prime! THEN or MIILS or RIEMANN hypothesis is FALSE.. or BOTH! G.I. —Preceding unsigned comment added by Imbalzanog (talk • contribs) 20:58, 29 August 2009 (UTC)

You don't have enough decimals of A in your calculations. Here are 600: A = 1.30637788386308069046861449260260571291678458515671\ 36443680537599664340537668265988215014037011973957\ 07296960938103086882238861447816353486887133922146\ 19435345787110033188140509357535583193264801721383\ 23615223590622186016108566790572151979760951619929\ 52797079925631721527841237130765849112456317518426\ 33105652153513186684155079079372385923352208421842\ 04053205176890260257934430086952906362056989687262\ 12274997876664385157661914387728449820775905648255\ 60915004123788524793626088046688154064374425340131\ 07361144094137650364379301267672117131030265228386\ 61546668804874760951441079075406984172603473107746

This precision gives 6 primes: 2, 11, 1361, 2521008887, 16022236204009818131831320183, 4113101149215104800030529537915953170486139623539759933135949994882770404074832568499. The 7th number is composite when A is "only" given to the 600 decimals above. PrimeHunter (talk) 21:50, 29 August 2009 (UTC)

Thank you, but inform the readers of this necessity. Besides, I am convinced that all this is an "artificial construction": we could get analogous results in many other ways, without importance for the mathematics... OK? G.I. —Preceding unsigned comment added by Imbalzanog (talk • contribs) 19:44, 30 August 2009 (UTC)

Formula for primes#Mills's formula says: "the smallest such A has a value of around 1.3063... and is known as Mills' constant". I don't see what more is neeed. "..." signals there are more decimals. Of course you don't get exact results if you only include some of the decimals. I don't see a good reason to mention exactly how many decimals are needed to get the right prime for n=4 when none of the primes for any n value is mentioned in Formula for primes. However, a couple of days ago I edited Mills' constant in to display the decimals required to get the primes listed in that article: 2, 11, 1361, 2521008887. Mills proved a non-trivial result which has interested many people and is mentioned in many reliable sources. I think it belongs here much more than many of the useless formulas to generate primes with convoluted expressions which are just equivalent to a very slow form of trial division. PrimeHunter (talk) 02:03, 31 August 2009 (UTC)

Now I agree, for the satisfactory article of citation. This confirms also my opinion, that the hypothesis of Riemann is dynamic: the hypothesis is true because and until we may build the mathematics... but in the same time the mathematics coherence is indefinite (Kurt Gödel). Imbalzanog (talk) 15:02, 2 September 2009 (UTC)


Problems with the proof at "Prime formulas and polynomial functions"

The proof that "no non-constant polynomial function P(n) exists that evaluates to a prime number for all integers n."

1. Assumes that all the coefficient of the polynomial are integers - which is not true see for example http://www.maa.org/editorial/mathgames/mathgames_07_17_06.html where there is a polynomial of order 5 with 57 conservative primes.

2. Is not simple at all - need more clarification. —Preceding unsigned comment added by 84.109.83.123 (talk) 19:59, 19 July 2010 (UTC)

Please study Venu Atiyolil formula. It gives the nth prime by polynomial with a condition that one needs to take the integral part of the result. In simple words, the result may be 5.00234567.... and the integral part is 5 which yield the 3rd prime so on and so forth to infinity . —Preceding unsigned comment added by 74.97.4.93 (talk) 01:27, 23 December 2010 (UTC)

Just checking

In the first sentence, the phrase "exactly and without exception"... that means "every prime, and no non-prime", yes? DS (talk) 13:19, 23 August 2010 (UTC)

The primes for n = 0, 1, 2, 3... are 41, 43, 47, 53, 61, 71 (in Euler formula)

Actually 41, 41, 43, 47, 53, 61, 71 ...... —Preceding unsigned comment added by 165.228.167.155 (talk) 04:02, 4 February 2011 (UTC)

Fixed in . The idea is to produce 40 distinct primes so for n − n + 41 it's n from 1 to 40 (there is a variation n + n + 41 where it's 0 to 39). PrimeHunter (talk) 04:25, 4 February 2011 (UTC)

Sabihi paper and revert war

wikipedia has a guideline WP:3RR to prevent revert wars. We appear to have one about the Sabihi paper. I had a look for for citations for the paper "A Novel Explicit Formula for Computing π(x), the Number of Primes" and I could not find any so it does not meet the standards for a Reliable source and may falls Original research. Rather than revert the matter needs to be discussed here on the talk page, or further actions pike page protection may be needed.--Salix (talk): 22:53, 3 November 2012 (UTC)

There is a discussion of this material at Wikipedia_talk:WikiProject_Mathematics. Deltahedron (talk) 07:31, 4 November 2012 (UTC)


About the Diophantine equations

since the link to the natural numbers gives two different definitions, i suggest to write that the solutions must be in non-negative integers (as in the original article) i suspect that no solution is known, am i right in thinking this? — Preceding unsigned comment added by 2A00:1620:C0:64:21C:61FF:FE03:A4C (talk) 13:41, 14 December 2012 (UTC)

Formula for the nth prime

In User:BenCawaling/Essay#Discussion_moved_from_Talk:Cantor.27s_theorem it is written: "here's a forula for the nth prime: p n = 1 + ∑ m = 1 2 n ⌊ ⌊ n 1 + ∑ j = 2 m ⌊ ( j − 1 ) ! + 1 j − ⌊ ( j − 1 ) ! j ⌋ ⌋   ⌋ 1 n ⌋ . {\displaystyle p_{n}=1+\sum _{m=1}^{2^{n}}\left\lfloor \left\lfloor {n \over 1+\sum _{j=2}^{m}\left\lfloor {(j-1)!+1 \over j}-\left\lfloor {(j-1)! \over j}\right\rfloor \right\rfloor \ }\right\rfloor ^{1 \over n}\right\rfloor .} " Jayme (talk) 14:42, 24 December 2012 (UTC)

old version

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is easily computable is presently known. A number of constraints are known: what such a "formula" can and cannot be.

Prime formulas and polynomial functions

It is known that no non-constant polynomial function P(n) with integer coefficients exists that evaluates to a prime number for all integers n. The proof is as follows: Suppose such a polynomial existed. Then P(1) would evaluate to a prime p, so P ( 1 ) ≡ 0 ( mod p ) {\displaystyle P(1)\equiv 0{\pmod {p}}} . But for any k, P ( 1 + k p ) ≡ 0 ( mod p ) {\displaystyle P(1+kp)\equiv 0{\pmod {p}}} also, so P ( 1 + k p ) {\displaystyle P(1+kp)} cannot also be prime (as it would be divisible by p) unless it were p itself, but the only way P ( 1 + k p ) = P ( 1 ) {\displaystyle P(1+kp)=P(1)} for all k is if the polynomial function is constant.

The same reasoning shows an even stronger result: no non-constant polynomial function P(n) exists that evaluates to a prime number for almost all integers n.

Euler first noticed (in 1772) that the quadratic polynomial

P(n) = n - n + 41

is prime for all positive integers less than 41. The primes for n = 1, 2, 3... are 41, 43, 47, 53, 61, 71... The differences between the terms are 2, 4, 6, 8, 10... For n = 41, it produces a square number, 1681, which is equal to 41×41, the smallest composite number for this formula. If 41 divides n it divides P(n) too. The phenomenon is related to the Ulam spiral, which is also implicitly quadratic, and the class number; this polynomial is related to the Heegner number 163 = 4 ⋅ 41 − 1 {\displaystyle 163=4\cdot 41-1} , and there are analogous polynomials for p = 2 , 3 , 5 , 11 ,  and  17 {\displaystyle p=2,3,5,11,{\text{ and }}17} , corresponding to other Heegner numbers.

It is known, based on Dirichlet's theorem on arithmetic progressions, that linear polynomial functions L ( n ) = a n + b {\displaystyle L(n)=an+b} produce infinitely many primes as long as a and b are relatively prime (though no such function will assume prime values for all values of n). Moreover, the Green–Tao theorem says that for any k there exists a pair of a and b with the property that L ( n ) = a n + b {\displaystyle L(n)=an+b} is prime for any n from 0 to k − 1. However, the best known result of such type is for k = 26:

43142746595714191 + 5283234035979900n is prime for all n from 0 to 25 (Andersen 2010).

It is not even known whether there exists a univariate polynomial of degree at least 2 that assumes an infinite number of values that are prime; see Bunyakovsky conjecture.

Formula based on a system of Diophantine equations

A system of 14 Diophantine equations in 26 variables can be used to obtain a Diophantine representation of the set of all primes. Jones et al. (1976) proved that a given number k + 2 is prime if and only if the following system of 14 Diophantine equations has a solution in the natural numbers:

α0 = w z + h + j − q {\displaystyle wz+h+j-q} = 0
α1 = ( g k + 2 g + k + 1 ) ( h + j ) + h − z {\displaystyle (gk+2g+k+1)(h+j)+h-z} = 0
α2 = 16 ( k + 1 ) 3 ( k + 2 ) ( n + 1 ) 2 + 1 − f 2 {\displaystyle 16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}} = 0
α3 = 2 n + p + q + z − e {\displaystyle 2n+p+q+z-e} = 0
α4 = e 3 ( e + 2 ) ( a + 1 ) 2 + 1 − o 2 {\displaystyle e^{3}(e+2)(a+1)^{2}+1-o^{2}} = 0
α5 = ( a 2 − 1 ) y 2 + 1 − x 2 {\displaystyle (a^{2}-1)y^{2}+1-x^{2}} = 0
α6 = 16 r 2 y 4 ( a 2 − 1 ) + 1 − u 2 {\displaystyle 16r^{2}y^{4}(a^{2}-1)+1-u^{2}} = 0
α7 = n + l + v − y {\displaystyle n+l+v-y} = 0
α8 = ( a 2 − 1 ) l 2 + 1 − m 2 {\displaystyle (a^{2}-1)l^{2}+1-m^{2}} = 0
α9 = a i + k + 1 − l − i {\displaystyle ai+k+1-l-i} = 0
α10 = ( ( a + u 2 ( u 2 − a ) ) 2 − 1 ) ( n + 4 d y ) 2 + 1 − ( x + c u ) 2 {\displaystyle ((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}} = 0
α11 = p + l ( a − n − 1 ) + b ( 2 a n + 2 a − n 2 − 2 n − 2 ) − m {\displaystyle p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m} = 0
α12 = q + y ( a − p − 1 ) + s ( 2 a p + 2 a − p 2 − 2 p − 2 ) − x {\displaystyle q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x} = 0
α13 = z + p l ( a − p ) + t ( 2 a p − p 2 − 1 ) − p m {\displaystyle z+pl(a-p)+t(2ap-p^{2}-1)-pm} = 0

The 14 equations α0, …, α13 can be used to produce a prime-generating polynomial inequality in 26 variables:

( k + 2 ) ( 1 − α 0 2 − α 1 2 − ⋯ − α 13 2 ) > 0 {\displaystyle (k+2)(1-\alpha _{0}^{2}-\alpha _{1}^{2}-\cdots -\alpha _{13}^{2})>0}

i.e.:

( k + 2 ) ( 1 − {\displaystyle (k+2)(1-}
[ w z + h + j − q ] 2 − {\displaystyle ^{2}-}
[ ( g k + 2 g + k + 1 ) ( h + j ) + h − z ] 2 − {\displaystyle ^{2}-}
[ 16 ( k + 1 ) 3 ( k + 2 ) ( n + 1 ) 2 + 1 − f 2 ] 2 − {\displaystyle ^{2}-}
[ 2 n + p + q + z − e ] 2 − {\displaystyle ^{2}-}
[ e 3 ( e + 2 ) ( a + 1 ) 2 + 1 − o 2 ] 2 − {\displaystyle ^{2}-}
[ ( a 2 − 1 ) y 2 + 1 − x 2 ] 2 − {\displaystyle ^{2}-}
[ 16 r 2 y 4 ( a 2 − 1 ) + 1 − u 2 ] 2 − {\displaystyle ^{2}-}
[ n + l + v − y ] 2 − {\displaystyle ^{2}-}
[ ( a 2 − 1 ) l 2 + 1 − m 2 ] 2 − {\displaystyle ^{2}-}
[ a i + k + 1 − l − i ] 2 − {\displaystyle ^{2}-}
[ ( ( a + u 2 ( u 2 − a ) ) 2 − 1 ) ( n + 4 d y ) 2 + 1 − ( x + c u ) 2 ] 2 − {\displaystyle ^{2}-}
[ p + l ( a − n − 1 ) + b ( 2 a n + 2 a − n 2 − 2 n − 2 ) − m ] 2 − {\displaystyle ^{2}-}
[ q + y ( a − p − 1 ) + s ( 2 a p + 2 a − p 2 − 2 p − 2 ) − x ] 2 − {\displaystyle ^{2}-}
[ z + p l ( a − p ) + t ( 2 a p − p 2 − 1 ) − p m ] 2 ) {\displaystyle ^{2})}
> 0 {\displaystyle >0}

is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables a, b, …, z range over the nonnegative integers.

A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables. Hence, there is a prime-generating polynomial as above with only 10 variables. However, its degree is large (in the order of 10). On the other hand, there also exists such a set of equations of degree only 4, but in 58 variables.(Jones 1982)

Formulas using the floor function

Using the floor function ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } (defined to be the largest integer less than or equal to the real number x), one can construct several formulas that take only prime numbers as values for all positive integers n.

Mills's formula

The first such formula known was established in 1947 by W. H. Mills, who proved that there exists a real number A such that

⌊ A 3 n ⌋ {\displaystyle \lfloor A^{3^{n}}\;\rfloor }

is a prime number for all positive integers n. If the Riemann hypothesis is true, then the smallest such A has a value of around 1.3063... and is known as Mills' constant. This formula has no practical value, because very little is known about the constant (not even whether it is rational), and there is no known way of calculating the constant without finding primes in the first place.

Converting the sieve of Eratosthenes to prime number formulas

There is another, quite different formula discovered by Sebastián Martín-Ruiz (Rivera n.d.) and proved with Jonathan Sondow (Martin-Ruiz & Sondow 2002):

π ( k ) = k − 1 + ∑ j = 1 k ⌊ 2 j ( 1 + ∑ s = 1 ⌊ j ⌋ ( ⌊ j − 1 s ⌋ − ⌊ j s ⌋ ) ) ⌋ {\displaystyle \pi (k)=k-1+\sum _{j=1}^{k}\left\lfloor {2 \over j}\left(1+\sum _{s=1}^{\left\lfloor {\sqrt {j}}\right\rfloor }\left(\left\lfloor {j-1 \over s}\right\rfloor -\left\lfloor {j \over s}\right\rfloor \right)\right)\right\rfloor }

Note the following equalities:

⌊ j s ⌋ − ⌊ j − 1 s ⌋ = { 1 s  divides  j 0 s  does not divide  j {\displaystyle \left\lfloor {j \over s}\right\rfloor -\left\lfloor {j-1 \over s}\right\rfloor ={\begin{cases}1&s{\text{ divides }}j\\0&s{\text{ does not divide }}j\end{cases}}}
2 ∑ s = 1 ⌊ j ⌋ ( ⌊ j s ⌋ − ⌊ j − 1 s ⌋ ) = number of divisors of  j {\displaystyle 2\sum _{s=1}^{\left\lfloor {\sqrt {j}}\right\rfloor }\left(\left\lfloor {j \over s}\right\rfloor -\left\lfloor {j-1 \over s}\right\rfloor \right)={\text{number of divisors of }}j}
⌊ − 1 j ∑ s = 2 ⌊ j ⌋ ( ⌊ j s ⌋ − ⌊ j − 1 s ⌋ ) ⌋ = { 0 j  is prime − 1 j  is composite {\displaystyle \left\lfloor {-1 \over j}\sum _{s=2}^{\left\lfloor {\sqrt {j}}\right\rfloor }\left(\left\lfloor {j \over s}\right\rfloor -\left\lfloor {j-1 \over s}\right\rfloor \right)\right\rfloor ={\begin{cases}0&j{\text{ is prime}}\\-1&j{\text{ is composite}}\end{cases}}}
IsPrime ⁡ ( j ) = 1 + ⌊ − 1 j ∑ s = 2 ⌊ j ⌋ ( ⌊ j s ⌋ − ⌊ j − 1 s ⌋ ) ⌋ = { 1 j  is prime 0 j  is composite {\displaystyle \operatorname {IsPrime} (j)=1+\left\lfloor {-1 \over j}\sum _{s=2}^{\left\lfloor {\sqrt {j}}\right\rfloor }\left(\left\lfloor {j \over s}\right\rfloor -\left\lfloor {j-1 \over s}\right\rfloor \right)\right\rfloor ={\begin{cases}1&j{\text{ is prime}}\\0&j{\text{ is composite}}\end{cases}}}
π ( k ) = ∑ j = 2 k IsPrime ⁡ ( j ) , {\displaystyle \pi (k)=\sum _{j=2}^{k}\operatorname {IsPrime} (j),}

where π ( k ) {\displaystyle \pi (k)} is the prime counting function.

Converting primality tests to prime number formulas

Any primality test can be used as the basis for a prime number formula. In effect, a test for the primality of n is a computation of the function IsPrime(n), defined by:

IsPrime ⁡ ( n ) = { 1 n  prime 0 n  composite {\displaystyle \operatorname {IsPrime} (n)={\begin{cases}1&n{\text{ prime}}\\0&n{\text{ composite}}\end{cases}}}

If the primality test is given by a condition on some formula involving n , {\displaystyle n,} then that formula gives a formula for IsPrime(n). Using a product,

∏ k = 2 n ∏ l = 2 n ( n − k l ) = 0  if and only if n is not a prime (and integer more than 1) {\displaystyle \prod _{k=2}^{n}\prod _{l=2}^{n}(n-kl)=0{\text{ if and only if n is not a prime (and integer more than 1)}}}

For a prime n ≥ 2 {\displaystyle n\geq 2} ,the product above is not 0. So,

IsPrime ⁡ ( n ) = abs ⁡ ( sgn ⁡ ( ∏ k = 2 n ∏ l = 2 n ( n − k l ) ) ) {\displaystyle \operatorname {IsPrime} (n)=\operatorname {abs} \left(\operatorname {sgn} \left(\prod _{k=2}^{n}\prod _{l=2}^{n}(n-kl)\right)\right)}

where n is more than 1. However, the product is very large or very small where n is a prime so

IsPrime ⁡ ( n ) = abs ⁡ ( ∏ k = 2 n ∏ l = 2 n sgn ⁡ ( n − k l ) ) . {\displaystyle \operatorname {IsPrime} (n)=\operatorname {abs} \left(\prod _{k=2}^{n}\prod _{l=2}^{n}\operatorname {sgn} (n-kl)\right).}

Moreover, we need not calculate product up to k=l=n.

IsPrime ⁡ ( n ) = abs ⁡ ( ∏ k = 2 ⌊ n 2 ⌋ ∏ l = 2 min ⁡ ( k , ⌊ n k ⌋ ) sgn ⁡ ( n − k l ) ) . {\displaystyle \operatorname {IsPrime} (n)=\operatorname {abs} \left(\prod _{k=2}^{\lfloor {\frac {n}{2}}\rfloor }\prod _{l=2}^{\operatorname {min} (k,\lfloor {\frac {n}{k}}\rfloor )}\operatorname {sgn} (n-kl)\right).}

Wilson's theorem states that n is prime if and only if it divides ( n − 1 ) ! + 1. {\displaystyle (n-1)!+1.} To express this by an explicit formula, two intermediate functions are introduced:

r ( n ) = ( n − 1 ) ! + 1 n , {\displaystyle r(n)={\frac {(n-1)!+1}{n}},}
IsInteger ⁡ ( x ) = { 1 x  is an integer 0 x  is not an integer {\displaystyle \operatorname {IsInteger} (x)={\begin{cases}1&x{\text{ is an integer}}\\0&x{\text{ is not an integer}}\end{cases}}}

Then Wilson's theorem says that

IsPrime ⁡ ( n ) = IsInteger ⁡ ( r ( n ) ) . {\displaystyle \operatorname {IsPrime} (n)=\operatorname {IsInteger} {\bigl (}r(n){\bigr )}.}

This can be further specified by an explicit formula for IsInteger(x). Some options are:

IsInteger ⁡ ( x ) = ⌊ x ⌋ + ⌊ − x ⌋ + 1 {\displaystyle \operatorname {IsInteger} (x)=\lfloor x\rfloor +\lfloor -x\rfloor +1}
IsInteger ⁡ ( x ) = ⌊ ⌊ x ⌋ x ⌋ {\displaystyle \operatorname {IsInteger} (x)=\left\lfloor {\frac {\lfloor x\rfloor }{x}}\right\rfloor }
IsInteger ⁡ ( x ) = ⌊ cos 2 ⁡ ( π x ) ⌋ {\displaystyle \operatorname {IsInteger} (x)=\lfloor \cos ^{2}(\pi x)\rfloor }  : formula by C. P. Willans (Bowyer n.d.)

Then, for example, taking the first option gives a formula for IsPrime(n) using Wilson's theorem:

IsPrime ⁡ ( n ) = ⌊ ( n − 1 ) ! + 1 n ⌋ + ⌊ − ( n − 1 ) ! + 1 n ⌋ + 1 {\displaystyle \operatorname {IsPrime} (n)=\left\lfloor {\frac {(n-1)!+1}{n}}\right\rfloor +\left\lfloor -{\frac {(n-1)!+1}{n}}\right\rfloor +1}

Not using the function IsInteger,

IsPrime ⁡ ( n ) = abs ⁡ ( ∏ k = 1 ( n − 1 ) ! sgn ⁡ ( ( n − 1 ) ! + 1 − k n ) ) . {\displaystyle \operatorname {IsPrime} (n)=\operatorname {abs} \left(\prod _{k=1}^{(n-1)!}\operatorname {sgn} ((n-1)!+1-kn)\right).}

Once IsPrime(n) can be computed, the prime counting function π ( n ) {\displaystyle \pi (n)} can as well, since by definition

π ( n ) = number of primes less than or equal to  n = ∑ k = 1 n IsPrime ⁡ ( k ) . {\displaystyle \pi (n)={\text{number of primes less than or equal to }}n=\sum _{k=1}^{n}\operatorname {IsPrime} (k).}

π ( n ) {\displaystyle \pi (n)} can then compute a function testing whether a given integer n is the m prime:

IsNthPrime ⁡ ( n , m ) = IsPrime ⁡ ( n ) ∗ IsZero ⁡ ( π ( n ) − m ) = { 1 n  is the  m th  prime 0 otherwise {\displaystyle \operatorname {IsNthPrime} (n,m)=\operatorname {IsPrime} (n)*\operatorname {IsZero} (\pi (n)-m)={\begin{cases}1&n{\text{ is the }}m^{\text{th}}{\text{ prime}}\\0&{\text{otherwise}}\end{cases}}}

The function IsZero(x) can likewise be expressed by a formula:

IsZero ⁡ ( n ) = ⌊ 1 1 + | n | ⌋ , {\displaystyle \operatorname {IsZero} (n)=\left\lfloor {1 \over {1+|n|}}\right\rfloor ,}

Finally, the IsNthPrime( n , m {\displaystyle n,m} ) function can be used to produce a formula for the n prime:

p n = ∑ m = 1 2 n m ∗ IsNthPrime ⁡ ( m , n ) . {\displaystyle p_{n}=\sum _{m=1}^{2^{n}}m*\operatorname {IsNthPrime} (m,n).}

The upper bound 2 comes from Bertrand's postulate, which implies that there is a sequence of primes

2 = p 1 < p 2 < ⋯ < p n , {\displaystyle 2=p_{1}<p_{2}<\dots <p_{n},} where p i + 1 < 2 p i . {\displaystyle p_{i+1}<2p_{i}.} Thus, p n < 2 n . {\displaystyle p_{n}<2^{n}.}

Substituting the formulas above and applying Wilson's theorem gives a formula for p n {\displaystyle p_{n}} involving the arithmetic operations and the floor function. Other such formulas are:

p n = 1 + ∑ k = 1 2 n ⌊ ⌊ n 1 + π ( k ) ⌋ 1 n ⌋ . {\displaystyle p_{n}=1+\sum _{k=1}^{2^{n}}\left\lfloor \left\lfloor {n \over 1+\pi (k)}\right\rfloor ^{1 \over n}\right\rfloor .}

in which the following equality is important:

⌊ ⌊ n 1 + π ( k ) ⌋ 1 n ⌋ = { 1 , if  π ( k ) ≤ n − 1 0 , if  π ( k ) > n − 1 {\displaystyle \left\lfloor \left\lfloor {n \over 1+\pi (k)}\right\rfloor ^{1 \over n}\right\rfloor ={\begin{cases}1,&{\text{if }}\pi (k)\leq n-1\\0,&{\text{if }}\pi (k)>n-1\end{cases}}}

and

p n = 1 + ∑ k = 1 2 ( ⌊ n ln ⁡ ( n ) ⌋ + 1 ) ( 1 − ⌊ π ( k ) n ⌋ ) {\displaystyle p_{n}=1+\sum _{k=1}^{2(\lfloor n\ln(n)\rfloor +1)}\left(1-\left\lfloor {\pi (k) \over n}\right\rfloor \right)}

by Sebastián Martín-Ruiz and proved with Jonathan Sondow (Martin-Ruiz & Sondow 2002). A similar formula for p n {\displaystyle p_{n}} was given earlier by Stephen Regimbal (Regimbal 1975).

Recurrence relation

Another prime generator is defined by the recurrence relation

a n = a n − 1 + gcd ⁡ ( n , a n − 1 ) , a 1 = 7 , {\displaystyle a_{n}=a_{n-1}+\operatorname {gcd} (n,a_{n-1}),\quad a_{1}=7,}

where gcd(x, y) denotes the greatest common divisor of x and y. The sequence of differences an + 1 − an starts with 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 (sequence A132199 in the OEIS). Rowland (2008) proved that this sequence contains only ones and prime numbers.

See also

References

External links

Prime number classes
By formula
By integer sequence
By property
Base-dependent
Patterns
k-tuples
By size
  • Mega (1,000,000+ digits)
  • Largest known
    • Complex numbers
    Composite numbers
    Related topics
    First 60 primes
    List of prime numbers
    Category:
    Talk:Formula for primes: Difference between revisions Add topic