Smooth polynomial formulas to produce all primes

[Cyclamen Persicum]

I have just downloaded the polynomial formula
to produce all primes. But I cannot compel it to work.
What's the matter?

f(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=
(k + 2)*(1 - (w*z + h + j - q)^2 - (2*n + p + q + z - e)^2 - (a^2*y^2 -
y^2 + 1 - x^2)^2 - ((e^4 + 2*e^3)*(a + 1)^2 -
o^2)^2 - (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 -
f^2)^2 - (((a + u^4 - u^2*a)^2 - 1)*(n + 4*d*y)^2 +
1 - (x + c*u)^2)^2 - (a*i + k + 1 - l -
i)^2 - ((g*k + 2*g + k + 1)*(h + j) + h -
z)^2 - (16*r^2*y^4*(a^2 - 1) + 1 - u^2)^2 - (p - m +
l*(a - n - 1) + b*(2*a*n + 2*a - n^2 - 2*n - 2))^2 - (z -
p*m + p*l*a - p^2*l + t*(2*a*p - p^2 - 1))^2 - (q - x +
y*(a - p - 1) +
s*(2*a*p + 2*a - p^2 - 2*p - 2))^2 - (a^2*l^2 - l^2 + 1 -
m^2)^2 - (n + l + v - y)^2)

[pakaran]

Maybe you should talk to the person you got this "formula" from?

I'd note that trying to produce all the primes without testing individual numbers is something people have been trying to do for centuries, without success.

I hope you forgive us for being slightly pessimistic.

[Xyzzy]

I sure wish this forum had a formula editor...

Maybe I'll toss that into Maple 7 and see what we get...

http://www.teamprimerib.com/gif/equation.gif

Hmm...

I told Maple to "solve" it and I got a really long weird-looking answer...

[cheesehead]

.

.


Spacing down a few lines to get out from under that last blurb ... there, that's better.

[eepiccolo]

Gee, I wish I had maple :( , that would be cool.

A polynomial function of 26 variables, which by amazing coincidence, is also the number of letters in the English language! Very convenient, we don't need to go to Greek letters for the function! I guess this is believable, since now we have physicists becoming experts in number theory because they have studied a limited sequence of primes :? .
http://www.nature.com/nsu/030317/030317-13.html

[cheesehead]

Originally Posted by Cyclamen Persicum

I have just downloaded the polynomial formula to produce all primes. But I cannot compel it to work. What's the matter?

This appears to be the same formula that was discussed in Mersenne Digest 313-314 with the subject "Big Equation". Here, I'll quote the formula from that discussion so some sharp-eyed youngster can verify that it's the same one:

f(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=

Originally Posted by STL137@aol.com, on Mersenne mailing list 16 Feb 1998

(k+2){1-[wz+h+j-q]²-[(gk+2g+k+1)(h+j)+h-z]²-[2n+p+q+z-e]²
-[16(k+1)³(k+2)(n+1)²+1-f²]²-[e³(e+2)(a+1)²+1-o²]²-[(a²-1)y²+1-x²]²
-[16r²y^4(a²-1)+1-u²]²-[((a+u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²]²
-[n+l+v-y]²-[(a²-1)l²+1-m²]²-[ai+k+1-l-i]²-[p+l(a-n-1)+b(2an+2a-n²-2n-2)-m]²
-[q+y(a-p-1)+s(2ap+2a-p²-2p-2)-x]²-[z+pl(a-p)+t(2ap-p²-1)-pm]²}

Stephen quoted it from CRC Standard Mathematical Tables and Formulae, 30th edition, page 94 and noted, "Anyway, the CRC book says that this "formula" produces all the prime numbers as it runs through all the positive integer values for all the variables. Unfortuantely, it also produces negative numbers, like -76."

It turns out that whenever the formula produces a positive value, that value is a prime.

Warwick Harvey wrote,

I remember being presented with a similar (quite possibly the same) expression when I did a number theory course 5 or 6 years ago. It was not a joke. My *memory* says that whenever the expression gave a positive value, that number was prime. The catch, of course, is that for most valuations of the 26 variables, it gave a negative value. Finding an assignment which gave a positive value should, presumably, be at least as hard as finding a prime number... ;)

I don't *think* it was claimed that the expression generated *all* primes, but I am not sure. I do remember the lecturer saying that the formula was, in essence, a clever mathematical encoding of a set of rules which guaranteed a number to be prime, and thus probably less useful for finding primes than using the original rules directly.

Note that formula has two factors: "k+2" and an expression consisting of 1 minus a set of squared terms. All variables are positive, and thus so is "k+2". Therefore the expression as a whole is positive exactly when the other factor is positive. Since each squared term is necessarily non-negative, this other factor is positive exactly when each of the terms evaluates to zero.

Andreas Eder added,

Well, the interesting thing is, that it does indeed produce all primes. And you are right, it is totally useless for finding primes. Its importance lies in the fact that there exists such a polynomial, makeing the primes a diophantine set. It all is a byproduct of Matijasevic's (spelling?) work on Hilbert's 10th problem. Read for example 'Logical Number Theory" a fascinating book about that topic. I forgot the name of the author; it is a springer book ...

Eric Brier noted,

Please note there exist an equation of the same form which gives the list of asll Mersenne primes. This equation is useless too.

Marc Thibeault wrote,

I heard of the "monster" polynomial to generate all primes some years ago. I also heard that some more simpler expressions were discovered later. If my memory does not play trick on me, I think that there exist some polynomials (in fact I am not sure if it is a polynome or something more complicated) with only five variables ...

Vincent Celier pointed out that the same formula is discussed on page 39 and 40 of the second edition of "Prime Numbers and Computer Methods for Factorization", by Hans Riesel, Birkhauser, ISBN 0-8176-3743-5 (c) 1994.

[eepiccolo]

Originally Posted by cheesehead

Here, I'll quote the formula from that discussion so some sharp-eyed youngster can verify that it's the same one

Well, they're almost equivalent, except for one term.
In the first equation, the fifth term is -((e^4 + 2*e^3)*(a + 1)^2 - o^2)^2
The sixth term in the second equation is the one that should be equivalent as far as I can tell, but that term is -[e³(e+2)(a+1)²+1-o²]²
Of course, there is a e³ factored out in the second term, but that's not the problem. The problem is the +1 in the second term that is not in the first term in any form. But other than that, the equations are equivalent. The +1 is probably from one of the equations not being copied properly.

Anyway, thanks for the clarification of the function Cheesehead, and sorry if I messed up your blurb spacing ;) .

[asdf]

Is there a name for this function? Sorry if I missed it in a previous post.
And are there any internet sites where I can find it?
asdf

[Cyclamen Persicum]

I see !!!
That's not a formula at all !!!
That's a great joke and kinda sieve.
Almost time it's negative,
but if not, it's equal to k+2 and other factor is 1.
As for me, I've tried a loop from 1 to 1000000
with all vars being random from 1 till 1000000,
but this stupid polynomial was always negative ! :D

[ewmayer]

Hans Riesel's book, "Prime Numbers and Computer Methods for Factorization"
has a nice discussion of these kinds of "prime-producing" polynomials. One of the earliest of these is Euler's famous x^2-x+41, which produces primes for x=0,1,2,...,40. This polynomial clearly cannot produce a prime for x=41, since in that case the -x+41 part is zero, leaving a perfect square. There is a more general proven theorem along these lines which applies to (non-constant) polynomials in arbitrarily many variables, namely that NO POLYNOMIAL CAN PRODUCE ONLY PRIMES.

However, it has also been proven that there do exist (non-polynomial) formulae which DO produce only primes. For example, Mills showed in 1947 that there exists a real number theta in (1,2), such that for every positive integer n, the number floor(theta^3^n) is prime. (Cf. the book by Crandall and Pomerance for more details and references). However, none of the known formulae of this type is practical for actually finding primes, in particular record-size primes.

[Cyclamen Persicum]

NO POLYNOMIAL CAN PRODUCE ONLY PRIMES.

But there are a lot of polynomials such that ALL of its POSITIVE values are primes !!!