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:
- A formula for as a function of .
- A formula for as a function of .
- A necessary and sufficient condition for to be prime.
- A function that is prime for each member of its domain.
- A function (the positive part of) whose range consists only of primes, or consists of all of the primes.
- A function whose range contains a high density of primes.
- A formula for the largest prime divisor of .
- A formula for the prime factors of .
- A formula for the smallest prime greater than .
- A formula for in terms of .
- An algorithm for generating the primes.
Similarly, Sato & Straus[3] propose 7 categories for prime-representing functions:
- Constant functions.
- Functions which are essentially equivalent to the definition of primes.
- Reinterpretation of (Eratosthenes) sieve method.
- Adding 1 -times where is prime.
- Functions which are constructed assuming prime sequence from the beginning.
- Analytic functions constructed by interpolation procedures.
- 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
References
- ↑ Jeffrey Shallit, No formula for the prime numbers?, January 07 2013 blog entry.
- ↑ Richard Guy, Unsolved Problems in Number Theory, 3 rd ed. (2004).
- ↑ Daihachiro Sato, E. G. Straus, “P‐Adic Proof of Non‐Existence of Proper Prime Representing Algebraic Functions and Related Problems,” J. London Math. Soc. (2), 2 (1970), pp. 45–48. © 2018 London Mathematical Society.
- ↑ Paulo Ribenboim, The Little Book of Bigger Primes, 2 nd ed. Springer 2004.
- ↑ Paulo Ribenboim, “Are there functions that generate prime numbers?,” College Mathematics Journal 28:5 (1997), pp. 352–359.
- ↑ Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press (August 1996).
- ↑ 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). [https://oeis.org/wiki/Formulas_for_primes]