2008-10-05

Prime number formulae

Last week, I was interviewed on ClassicFM in the show The Internet Economy about GIMPS - the Great Internet Mersenne Prime Search. During the interview, I said that there was no formula for generating prime numbers, by which I meant - of course - that there is no easy formula. As Eric Weisstein writes in the authoritative MathWorld,
"all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula."

He is writing about formulae that are known to produce the n-th prime p(n) on input n. There are other kinds of prime-generating formulae. Consider, for example, the formula described by Eric Rowland in a recent issue of the Journal of Integer Sequences. Rowland's sequence is defined by

a(n) = a(n-1) + gcd(n, a(n-1))

and a(1) = 7. He shows that the values taken on by a(n)-a(n-1) are always either one or prime. However, it is not known whether all primes are produced by this sequence, and I expect it not to be the case! Another approach is to consider the values taken on by a polynomial with integer coefficients and in several unknowns. There exist polynomials for which all the positive values are all prime and in fact there exist such polynomials for which all prime numbers are found among the positive values. These prime-generating polynomials (about which more in the MathWorld article cited below) are, however, not a particularly efficient way of generating prime numbers.


Sources

  1. Podcast of the 3 October 2008 edition of The Internet Economy on ClassicFM http://tinyurl.com/3m2gug

  2. Weisstein, Eric W. "Prime Formulas." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PrimeFormulas.html

  3. Rowland, Eric S. "A Natural Prime-Generating Recurrence." Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8 http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html

  4. Weisstein, Eric W. "Prime-Generating Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

1 opmerking:

Anoniem het gesĂȘ...

haai daar, petrus
kyk ook in daniel tammet se eerste boek, born on a blue day. jy weet ek glo nie aan getalle nie, maar tammet se beskrywing (priemgetalle as spoelklippe in sy numeriese landskappe) is wonderlik.