Talk:Formula for primes

From Wikipedia, the free encyclopedia

1 Formulas that frequently produce primes
2 Reversion of changes by an anon
3 Removal of formula
4 Correct formula
5 (n+1)th
6 Concerning the paper of Venu Atiyolil
7 Error in Formula based on a system of Diophantine equations
8 Polynomial formulaes --> editing a bit
9 Moved formula from article
- 9.1 Formula elaborated by Lainé Jean Lhermite Junior
10 Polynomial equations
11 Goldbach's
12 Formula based on Wilson's theorem

[edit] 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)

[edit] 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)

[edit] 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!)) \,\operatorname{mod} (n+1)].$

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 ([1]) 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

. This is equivalent to saying that the modulus

n + 1

is prime. Then:

$f(n) = 2 + [2n! \,\operatorname{mod} (n+1)] = 2 + [2(p - 1)! \,\operatorname{mod} ((p - 1)+1)]$

Applying Wilson's theorem, we get:

$f(n) = 2 + [2(-1)\,\operatorname{mod}\,p] = 2 + (-2\,\operatorname{mod}\,p) = 2 + (p - 2) = p$

So clearly, when the modulus

n + 1

is a prime p,

f (n) = p

, so when

n + 1

is prime,

f (n)

ranges over all the primes.

Now, we still have to prove that when

n + 1

is not prime, we get

f (n) = 2

. To prove this, all we need to do is show that $n! \,\operatorname{mod} (n+1) \equiv 0$ , since then that term drops out, leaving only the 2. We proceed to do this:

n + 1

is not prime, then we can write

n + 1 = p k

, where p is the smallest prime that divides

n + 1

. Clearly, since p and k are both factors of

n + 1

, we have

p < n + 1

and

k < n + 1

. Unless

p = k

, both p and k are distinct factors of the expansion $n! = n \times (n - 1) \times (n - 2) \times ... \times 1$ , implying that $n!\,{mod}\,(pk) \equiv n!\,{mod}\,(n + 1) \equiv 0$ .

Now, let's take the final case, where

n + 1 = p k

and

p = k

, that is, wherein

n + 1 = p 2

. We know

p < n + 1

, since p is the square root of

n + 1

, and

2 p < n + 1

, since for all integers $m \ge 3$ ,

2 m < m 2

. Therefore, the expansion $n! = n \times (n - 1) \times (n - 2) \times ... \times 1$ contains both 2p and p, so

p 2 | n!

and $n!\,{mod}\,(p^2) \equiv n!\,{mod}\,(n + 1) \equiv 0$ . QED.

—Lowellian (reply) 04:19, 26 May 2006 (UTC)

[edit] 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 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \pi(m) } \right\rfloor^{1 \over n} \right\rfloor.$

[edit] (n+1)th

"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)

The entire section is quite useless. I'm sufficiently new to Wikipedia to hesitate to delete it, but I wish that someone would.

I also hesitate to include a reference to my paper, "Formulas for primes" by Underwood Dudley (Mathematics Magazine 56 (1983), 17-22), but having it in the article would be nice, too.

The previous unsigned comment was added by Ddunx46135 00:30, 21 November 2006 (UTC), and reformatted by me for clarity. PrimeHunter 01:15, 21 November 2006 (UTC)

[edit] 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

[edit] 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-α₁²-α₂²-...-α₁₄²). 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)

[edit] Polynomial formulaes --> 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

[edit] 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" [2] PrimeHunter 01:03, 8 August 2007 (UTC)

[edit] Formula elaborated by Lainé Jean Lhermite Junior

$P_n = \sum_{i=1}^{2^n}h(i)$

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

$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)$

[edit] Polynomial equations

Hank Harrell has done work in this area [3] 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)

[edit] Goldbach's

in effect, [Goldbach's conjecture] 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 [d,N1,N2 are all positive integers]

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

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

[Another solution (3,61) exists outside of the conditions prescribed above ]

Similarly, (32,32) generates the same (4) pairs as 32+32 =39+25 (identical sums)
It generates "varied" bounded primes [unsure if every prime gets generated (imagine so)]--Billymac00 (talk) 22:17, 6 March 2008 (UTC)

[edit] 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!!

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)