 mersenneforum.org > Math Smooth polynomial formulas to produce all primes
 Register FAQ Search Today's Posts Mark Forums Read 2003-03-27, 13:47 #1 Cyclamen Persicum   Mar 2003 1218 Posts Smooth polynomial formulas to produce all primes 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)   2003-03-27, 15:36 #2 pakaran   Aug 2002 3×83 Posts 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.   2003-03-27, 15:43 #3 Xyzzy   "Mike" Aug 2002 2×19×199 Posts 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...   2003-03-27, 16:28 #4 cheesehead   "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts Spacing down a few lines ... . . Spacing down a few lines to get out from under that last blurb ... there, that's better.   2003-03-27, 16:32 #5 eepiccolo   Dec 2002 Frederick County, MD 5628 Posts What a coincidence! 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   2003-03-27, 16:44   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts Re: Smooth polynomial formulas to produce all primes

Quote:
 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)=
Quote:
 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,
Quote:
 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.
Quote:
 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,
Quote:
 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,
Quote:
 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.   2003-03-27, 17:52   #7
eepiccolo

Dec 2002
Frederick County, MD

5628 Posts Re: Smooth polynomial formulas to produce all primes

Quote:
 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 ;) .   2003-03-28, 03:53 #8 asdf   Sep 2002 22×3×5 Posts 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   2003-03-28, 11:35 #9 Cyclamen Persicum   Mar 2003 34 Posts 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   2003-03-28, 17:28 #10 ewmayer ∂2ω=0   Sep 2002 República de California 33·419 Posts 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.   2003-03-29, 07:08   #11
Cyclamen Persicum

Mar 2003

34 Posts Quote:
 NO POLYNOMIAL CAN PRODUCE ONLY PRIMES.
But there are a lot of polynomials such that ALL of its POSITIVE values are primes !!!  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post skan Miscellaneous Math 6 2012-12-14 12:56 alpertron Forum Feedback 4 2011-05-26 20:37 Lee Yiyuan Miscellaneous Math 60 2011-03-01 12:22 Unregistered Information & Answers 2 2011-01-14 17:19 drake2 Math 13 2006-10-10 00:43

All times are UTC. The time now is 02:01.

Thu Jul 16 02:01:58 UTC 2020 up 112 days, 23:35, 0 users, load averages: 1.92, 1.65, 1.55