mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-03-27, 13:47   #1
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

1218 Posts
Default 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)
Cyclamen Persicum is offline   Reply With Quote
Old 2003-03-27, 15:36   #2
pakaran
 
pakaran's Avatar
 
Aug 2002

3×83 Posts
Default

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.
pakaran is offline   Reply With Quote
Old 2003-03-27, 15:43   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×19×199 Posts
Default

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...
Xyzzy is offline   Reply With Quote
Old 2003-03-27, 16:28   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default Spacing down a few lines ...

.

.


Spacing down a few lines to get out from under that last blurb ... there, that's better.
cheesehead is offline   Reply With Quote
Old 2003-03-27, 16:32   #5
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

5628 Posts
Default 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
eepiccolo is offline   Reply With Quote
Old 2003-03-27, 16:44   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default 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.
Andreas Eder added,
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.
cheesehead is offline   Reply With Quote
Old 2003-03-27, 17:52   #7
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

5628 Posts
Default 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 ;) .
eepiccolo is offline   Reply With Quote
Old 2003-03-28, 03:53   #8
asdf
 
asdf's Avatar
 
Sep 2002

22×3×5 Posts
Default

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
asdf is offline   Reply With Quote
Old 2003-03-28, 11:35   #9
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

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
Cyclamen Persicum is offline   Reply With Quote
Old 2003-03-28, 17:28   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

33·419 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2003-03-29, 07:08   #11
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

Quote:
NO POLYNOMIAL CAN PRODUCE ONLY PRIMES.
But there are a lot of polynomials such that ALL of its POSITIVE values are primes !!!
Cyclamen Persicum is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
compendium of formulas related with primes ? skan Miscellaneous Math 6 2012-12-14 12:56
Problems for displaying math formulas alpertron Forum Feedback 4 2011-05-26 20:37
Assorted formulas for exponents of Mersenne primes Lee Yiyuan Miscellaneous Math 60 2011-03-01 12:22
recurrent formulas to obtain primes Unregistered Information & Answers 2 2011-01-14 17:19
Arithmetic and Polynomial Progression of Primes? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.