Dan Harmon <harmon@tenet.edu> writes:

If you find out anything would you please post it to the list? This is very curious.

D.C. Williams remembered the thread and Emailed me a copy. (Thanks D.C.) It was in alt.security.pgp which is why I couldn't find it. I was looking in sci.math for something with the word "prime" in the title. :) I quote the interesting sections below. Nick Gilling begins by asking:

Is there a formula for calculating primes?

Gareth McCaughan responds:

Well... yes, actually, but not a useful one.

For instance: "Wilson's theorem" says that if p is prime then (p-1)! is congruent to -1, modulo p. And you can check that if p isn't prime then (p-1)! is congruent to 0 modulo p (i.e., is a multiple of p).

So, writing [x] for "integer part of x", ((p-1)! - [(p-1)!/p].p)/(p-1) is 1 if p is prime and 0 if p is composite. So summing this thing will give you a formula for the number of primes <= any given number; and I'm sure there's a "formulaic" way to invert this to give you the n'th prime for any n.

Alternatively, there is a polynomial of degree something-very-large in about 26 variables with the property that when you plug integers into it you get either a negative number or a prime; and every prime arises as some value of it. (In fact, for any computable property of positive integers, there is a polynomial in lots of variables such that the values it takes are {some load of negative numbers} together with {positive integers with the required property}. This is a Deep Theorem.)

Alternatively, I suspect there is some sort of thing involving contour integrals and the Riemann zeta function.

James Kilfiger then expands:

Actually it a little more interesting than this. First a disclaimer, I'm writing from memory and may be wrong on details If you want to see more a truly wonderful book is "The Little book of BIG primes" By Riemboiem (I've spelt this wrong) published by Springer-Verlag.

This book as a section on prime number formulae, There is a famous class of polynomials {P(x)}, tend to be large (the classic one has 26 variables and has degree 25) With the exellent property of {all positive values taken by P(x)}={all positive primes}. The existance of such polynomials is gaurrenteed by results stemming from Hilbert's 10th. Also There is a number \theta with 3^\theta^n (or some similar formula, remeber I'm quoting from memory) being prime for all values of n, unfortuantly we can't calculate \theta, but its quite small. (if somebody can correct me on the formula I'd be grateful)

Gareth McCaughan then cites the following reference:

By an amusing coincidence, when I went into our departmental library to look for a reference, there on the "new accessions" shelf was a book all about Hilbert's tenth problem. So, here's a reference.

Matiyasevich, Yuri V. "Hilbert's 10th Problem" (MIT Press, 1993; in their "Foundations of Computing" series) section 3.4, at end.

For those who are wondering how on earth it's done, here's a *very* brief sketch. In everything that follows polynomials have integer coefficients, and variables range over non-negative integers, which I shall call "natural numbers".

Observation number 1: Suppose we have a set A of natural numbers, and a polynomial P such that: there exist x1,x2,..,xm with P(a,x1,..,xm)=0 iff a is in A. Then there is a polynomial Q such that the natural number values of Q(x0,..,xm) are just the elements of A. PROOF: put Q(x0,..,xm) = (x0+1)(1-P(x0,..,xm)^2)-1 and notice that if P isn't zero there, we get something negative, and if P is zero we get x0.

Difficult Theorem number 1: There is a polynomial E such that there exist x1,x2,..,xm with E(a,b,c,x1,..,xm)=0 if and only if a^b=c.

Observation number 2: So it's enough to find an "exponential polynomial" (i.e., we allow variables as exponents) such that there exist x1,..,xm with P(a,x1,..,xm)=0 if and only if a is prime.

Difficult Theorem number 2: We can "do" the operations "factorial" and "greatest common divisor" with exponential polynomials.

Easier Theorem: p is prime iff the greatest common divisor of p and (p-1)! is 1. (See a posting I made earlier in this thread.)

Conclusion: We can "do" primality with an exponential polynomial, and hence with a normal polynomial.

Annoying Fact: The numbers do get *very* large. I do not recommend trying to generate primes with this method. I haven't done the calculations, but I suspect that getting the prime 5 might require more computing resources than you have available.

More details are in Matiyasevich's book. (Matiyasevich did a large fraction of the work required to prove all this and much more. He knows what he is talking about.)

Victor S. Miller, [who I suspect is the same Victor S. Miller I knew at UMass Boston many years ago], published a nifty little paper in the mid 1980's on the computation of the function Pi(n) which gives the Nth prime as a function of N. He had a table giving the (10^N)th prime for n={3,6,9,12,15,18,...} which was quite impressive. Calculating the correct value for the zillionth prime directly is a cute bit of mathematics. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $