This site is supported by donations to The OEIS Foundation.

Formulas for primes

From OeisWiki
Jump to: navigation, search

There is a longstanding myth that there is no formula for prime numbers.[1] In fact, there are hundreds of formulas for primes of many different types. Guy devotes an entire section, A17 (with over a hundred references!), of his book[2] to formulas for primes, dividing them into 11 categories:

  1. A formula for as a function of x.
  2. A formula for as a function of n.
  3. A necessary and sufficient condition for n to be prime.
  4. A function that is prime for each member of its domain.
  5. A function (the positive part of) whose range consists only of primes, or consists of all of the primes.
  6. A function whose range contains a high density of primes.
  7. A formula for the largest prime divisor of n.
  8. A formula for the prime factors of n.
  9. A formula for the smallest prime greater than n.
  10. A formula for in terms of .
  11. An algorithm for generating the primes.

Similarly, Sato & Straus[3] propose 7 categories for prime-representing functions:

  1. Constant functions
  2. Functions which are essentially equivalent to the definition of primes
  3. Reinterpretation of (Eratosthenes) sieve method
  4. Adding 1 p-times where p is prime
  5. Functions which are constructed assuming prime sequence from the beginning
  6. Analytic functions constructed by interpolation procedures
  7. Use of Wilson's theorem or similar formulas which characterize prime numbers

Beside Guy, other collections of prime formulas can be found in Ribenboim[4][5], Bach & Shallit[6], and Lopez-Ortiz.[7]

See also


  1. Jeffrey Shallit, No formula for the prime numbers?, January 07 2013 blog entry.
  2. Richard Guy, Unsolved Problems in Number Theory, third edition (2004).
  3. Cite error: Invalid <ref> tag; no text was provided for refs named SatoStraus1970
  4. Paulo Ribenboim, The Little Book of Bigger Primes, second edition. Springer 2004.
  5. Paulo Ribenboim, Are there functions that generate prime numbers?, College Mathematics Journal 28:5 (1997), pp. 352–359.
  6. Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press (August 1996).
  7. Alex Lopez-Ortiz, ed., Formulae to compute prime numbers (1998). Part of The Sci.Math FAQ Team's Frequently Asked Questions in Mathematics.

Cite this page as

Charles R Greathouse IV, Formulas for primes.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). []