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.
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.
Related courses (10)
MATH-521: Advanced analytic number theory
We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
MATH-313: Number theory I.b - Analytic number theory
The aim of this course is to present the basic techniques of analytic number theory.
Show more
Related lectures (61)
Local Rings and Minimal Primes
Explores local rings, Noetherian rings, and minimal primes in the context of integral domains.
Primes in Arithmetic Progression
Explores primes in arithmetic progression, focusing on L-functions, characters, and the divergence of the sum of 1 over p for p congruent to a modulo q.
Commutation Groups: Euler's Totient Function
Explores commutative groups, Euler's Totient Function, and Cartesian products in group theory.
Show more
Related publications (42)

Non-planarity of Markoff graphs mod p

Matthew De Courcy-Ireland

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...
Berlin2024

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...
SPRINGER HEIDELBERG2022

A new elementary proof of the Prime Number Theorem

Florian Karl Richter

Let Ω(n)\Omega(n) denote the number of prime factors of nn. We show that for any bounded f ⁣:NCf\colon\mathbb{N}\to\mathbb{C} one has [ \frac{1}{N}\sum_{n=1}^N, f(\Omega(n)+1)=\frac{1}{N}\sum_{n=1}^N, f(\Omega(n))+\mathrm{o}_{N\to\infty}(1). ] This yields a ...
2021
Show more
Related concepts (1)
Prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.