Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Formula for primes
Summary
In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be.
A simple formula is
for positive integer , where is the floor function, which rounds down to the nearest integer.
By Wilson's theorem, is prime if and only if . Thus, when is prime, the first factor in the product becomes one, and the formula produces the prime number . But when is not prime, the first factor becomes zero and the formula produces the prime number 2.
This formula is not an efficient way to generate prime numbers because evaluating requires about multiplications and reductions modulo .
In 1964, Willans gave the formula
for the th prime number .
This formula reduces to ; that is, it tautologically defines as the smallest integer m for which the prime-counting function is at least n. This formula is also not efficient. In addition to the appearance of , it computes by adding up copies of ; for example, .
The articles What is an Answer? by Herbert Wilf (1982) and Formulas for Primes by Underwood Dudley (1983) have further discussion about the worthlessness of such formulas.
Because the set of primes is a computably enumerable set, by Matiyasevich's theorem, it can be obtained from a system of Diophantine equations. found an explicit set of 14 Diophantine equations in 26 variables, such that a given number k + 2 is prime if and only if that system has a solution in nonnegative integers:
The 14 equations α0, ..., α13 can be used to produce a prime-generating polynomial inequality in 26 variables:
That is,
is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables a, b, ..., z range over the nonnegative integers.
A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.