                                Prime Formulas    There exist a variety of formulas for either producing the nth prime as a function of n or taking on only prime values. However, 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 (Dudley 1969, Ribenboim 1996, p. 186). There also exist simple prime-generating polynomials that exclusively primes exclusively for the first (possibly large) number of integer values.

Considering examples of formulas that produce only prime numbers (although not necessarily the complete set of prime numbers P), there exists a constant (Sloane's A051021) known as Mills' constant such that (1)

where is the floor function, is prime for all (Ribenboim 1996, p. 186). The first few values of f(n) are 2, 11, 1361, 2521008887, ... (Sloane's A051254). It is not known if is irrational. There also exists a constant such that (2)

(Wright 1951; Ribenboim 1996, p. 186) is prime for every . The first few values of g(n) are 3, 13, 16381, .... In the case of both f(n) and g(n), the numbers at n = 4 grow so rapidly that an extremely precise value of or is needed in order to obtain the correct value, and values for are effectively incomputable.

There follow a number of explicit formulas for explicitly computing the nth prime. However, it should again be emphasized that these formulas are extremely inefficient, and in many (if not all) cases, simply performing an efficient sieving would yield the primes much more quickly and efficiently. Explicit formulas exist for the nth prime both as a function of n and in terms of the primes 2, ..., (Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41). Let (3)

for integral j > 1, where is again the floor function. Then   (4)  (5)

where is the prime counting function. This formula conceals the prime numbers j as those for which , i.e., the values of F(j) are 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ....

Gandhi gave the formula in which is the unique integer such that (6)

where is the primorial function (Gandhi 1971, Eynden 1972, Golomb 1974) and is the Möbius function. It is also true that (7)

(Ribenboim 1996, pp. 180-182). Note that the number of terms in the summation to obtain the nth prime is , so these formulas turn out not to be practical in the study of primes. An interesting infinite product formula due to Euler that relates and the nth prime is   (8)  (9)

(Blatner 1997). Hardy and Wright (1979, p. 414) give the formula (10)

for n > 3, where (11)

and an "elementary" formula for the prime counting function is given by (12)

(correcting a sign error), where is the floor function.

A double sum for the nth prime is (13)

where (14)

(Ruiz 2000).

B. M. Bredihin proved that (15)

takes prime values for infinitely many integral pairs (x, y) (Honsberger 1976, p. 30). In addition, the function (16)

where (17) is the factorial, and is the floor function, generates only prime numbers for positive integer arguments. It not only generates every prime number, but generates odd primes exactly once each, with all other values being 2 (Honsberger 1976, p. 33). For example,   (18)   (19)   (20)

with no new primes generated for .

The FRACTRAN game (Guy 1983, Conway and Guy 1996, p. 147) provides an unexpected means of generating the prime numbers based on 14 fractions, but it is actually just a concealed version of a sieve. FRACTRAN, Mills' Constant, Prime Counting Function, Prime Number, Sieve Blatner, D. The Joy of Pi. New York: Walker, p. 110, 1997.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 130 and 147, 1996.

Dudley, U. "History of Formula for Primes." Amer. Math. Monthly 76, 23-28, 1969.

Finch, S. "Favorite Mathematical Constants." http://pauillac.inria.fr/algo/bsolve/constant/mills/mills.html.

Gandhi, J. M. "Formulae for the Nth Prime." Proc. Washington State University Conferences on Number Theory. pp. 96-107, 1971.

Gardner, M. "Patterns and Primes." Ch. 9 in The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 79-90, 1984.

Guy, R. K. "Conway's Prime Producing Machine." Math. Mag. 56, 26-33, 1983.

Guy, R. K. "Prime Numbers," "Formulas for Primes," and "Products Taken over Primes." Ch. A, §A17, and §B48 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 3-43, 36-41, and 102-103, 1994.

Hardy, G. H. and Wright, E. M. "Prime Numbers" and "The Sequence of Primes." §1.2 and 1.4 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 1-4, 5-6, 344-345, and 414, 1979.

Honsberger, R. Mathematical Gems II. Washington, DC: Math. Assoc. Amer., 1976.

Mills, W. H. "A Prime-Representing Function." Bull. Amer. Math. Soc. 53, 604, 1947.

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, 1996.

Ruiz, S. M. "The General Term of the Prime Number Sequence and the Smarandache Prime Function." Smarandache Notions J. 11, 59-61, 2000.

Sloane, N. J. A. Sequences A051021 and A051254 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.

Wright, E. M. "A Prime-Representing Function." Amer. Math. Monthly 58, 616-618, 1951.

Author: Eric W. Weisstein    