Prime Formulas

Prime formulas either produce the th prime number as a function of or take only prime values on a specified domain. Many require extremely accurate knowledge of a constant or encode inefficient primality tests (Dudley 1969; Ribenboim 1996, p. 186). There also exist simple prime-generating polynomials that generate only primes for the first (possibly large) number of integer values.

There are also many beautiful formulas involving prime sums and prime products that can be done in closed form.

Considering examples of formulas that produce only prime numbers (although not necessarily the complete set of prime numbers ), there exists a constant such that

where is the floor function, is prime for all (Ribenboim 1996, p. 186). The least such is Mills' constant, which is irrational (Saito 2025). Assuming the Riemann hypothesis, it begins (OEIS A051021), and the first few values of are 2, 11, 1361, 2521008887, 16022236204009818131831320183, ... (OEIS A051254; Caldwell and Cheng 2005, p. 5). There also exists a constant (OEIS A086238) such that

(Wright 1951; Ribenboim 1996, p. 186) is prime for every . The first few values of are 3, 13, 16381, ... (OEIS A016104). Both formulas produce rapidly growing numbers and require increasingly precise values of or . Caldwell and Cheng (2005, pp. 5-6) computed the first ten terms of the Mills sequence, determining its constant to 6850 decimal places under the Riemann hypothesis.

Explicit formulas exist for the th prime both as a function of and in terms of the primes 2, ..., (Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41), a number of which are given below. 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.

A prime-generating formula sometimes known as Willans' formula can be constructed as follows. Let

for a positive integer , where is again the floor function. This formula is a consequence of Wilson's theorem and conceals the prime numbers as those for which , i.e., the values of are 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ... (OEIS A080339). Then

for , and

for a positive integer , where is the prime counting function (Willans 1964; Havil 2003, pp. 168-169).

Gandhi gave the formula in which is the unique integer such that

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

for . Each product is 1 until the first prime number after is reached and is 0 thereafter. Bertrand's postulate ensures that this prime number occurs before . In Willans' formula, the sum contains terms, so it is not a practical method of finding the th prime number.

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

for , where

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

for an integer , where is the floor function.

A double sum for the th prime is

where

(Ruiz 2000).

Ruiz and Sondow (2014, pp. 96-97) give the simpler form

for an integer , where is the prime counting function. Their proof uses inequalities of Rosser and Schoenfeld to establish . Within the summation range, the summand is 1 for and 0 for , so the sum is .

An asymptotic formula for is given by

(Cipolla 1902). This asymptotic expansion is the inverse of the logarithmic integral obtained by series reversion, where the inversion of gives because the prime number theorem says that , where is the prime counting function and the inverse of is in the sense that . However, the formula oscillates a great deal as illustrated above, where is the difference between the actual th prime and that given by the Cipolla formula. Interestingly, truncating at gives the refined form of Rosser's theorem, which is a strict inequality on . Salvy (1994) deals with more general cases.

B. M. Bredihin proved that

takes prime values for infinitely many pairs of positive integers (Honsberger 1976, p. 30). For example, , , , and so on. The primes of this form are 3, 11, 19, 41, 53, 59, 73, 83, 101, 107, 131, 137, 149, 163, ... (OEIS A079544; Mitrinović and Sándor 1995, p. 11). The values of and for which is prime are plotted above, showing some interesting patterns.

It is in general not difficult to artificially construct formulas that always generate prime numbers. For example, consider the formula

where

is the factorial, and and are positive integers (Honsberger 1976, p. 33). Whenever , it has and yields the value 2. The remaining case is and , in which case it simplifies to

The formula therefore generates odd primes exactly once each (Honsberger 1976, p. 33) at the values for which the Wilson quotient is an integer, i.e., 1, 1, 5, 103, 329891, 36846277, 1230752346353, ... (OEIS A007619).

Bouras (2022) introduced a sequence taking only the value 1 or a prime number. Cloitre (2025, pp. 1-4) proved that it has the simpler representation

for an integer , where is the greatest common divisor and is a factorial. Its first terms are 1, 5, 11, 19, 29, 41, 11, 71, 89, 109, 131, 31, 181, ... (OEIS A356247). The prime numbers that occur are exactly 5 and those ending in 1 or 9 in decimal notation. The value 5 occurs once, at , and every other prime number in the sequence occurs twice.

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.