Prime number generator

In computer science, a prime number generator is an algorithm so that for natural numbers the value is the -th prime number . In mathematics and especially in number theory, this corresponds to formulas that produce a particularly large number of prime numbers (formulas for prime numbers). So far, no efficient prime number generator has been found, in particular there is no practicable closed formula for generating prime numbers. ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle n}$

However, there are formulas where there is a certain probability that a generated number is a prime number, so that the generated numbers still have to be tested to see whether they are prime. The article also deals with other formulas that are not practical, but which have been discussed in the mathematical literature regarding the question of whether they yield many prime numbers.

history

One of the oldest algorithms for determining prime numbers is the sieve of Eratosthenes , in which those numbers are deleted one after the other from a list of natural numbers that are multiples of the smallest number that has not yet been deleted. This leaves the prime numbers in the initial list.

Euler already gave the formulas and that yield prime numbers for and . The two formulas also return many prime numbers for larger values ​​of , because the result can never be divided by prime numbers or whole numbers . In general, there are many such formulas , which explains the eye-catching Ulam spiral . According to Adrien-Marie Legendre , however, there is no polynomial that yields prime numbers for all values ​​of the variables in the natural numbers (not even almost all prime numbers). The question of which integer polynomials produce an infinite number of prime numbers is the subject of the Bunjakowski conjecture . ${\displaystyle n^{2}+n+17}$ ${\displaystyle n^{2}-n+41}$ ${\displaystyle 0\leq n<16}$ ${\displaystyle 0\leq n<41}$ ${\displaystyle n}$ ${\displaystyle p<17}$ ${\displaystyle p<41}$ ${\displaystyle an^{2}+bn+c}$

The most popular is that of the Mersenne number , which is a prime number. The special properties of the divisors of Mersenne numbers make them suitable for searching for the largest possible prime numbers. ${\displaystyle M_{n}=2^{n}-1}$ ${\displaystyle M_{n}}$

Fermat hypothesized that all numbers of the form are prime; they are called Fermat numbers . In fact, no such prime number is known. ${\displaystyle 2^{2^{n}}+1}$ ${\displaystyle n>4}$

An application of Euclid's theorem is also known, in which a 1 is added to the primorial (product of all prime numbers from 2 to ): ${\displaystyle p\#}$ ${\displaystyle p}$

${\displaystyle p\#+1=2\cdot 3\cdot 5\dotsm p+1}$

${\displaystyle p\#+1}$is prime for (sequence A005234 in OEIS ) It is unknown whether there are an infinite number of prime numbers that can be generated in this way. ${\displaystyle p=2,3,5,7,11,31,379,1019,1021,\dotsc }$

More formulas

• ${\displaystyle n!-1}$is prime for (sequence A002982 in OEIS ) ${\displaystyle n=3,4,6,7,12,14,30,32,33,38,94,166,\dotsc }$
• ${\displaystyle n!+1}$is prime for (sequence A002981 in OEIS ) ${\displaystyle n=1,2,3,11,27,37,41,73,77,116,154,\dotsc }$
• Prime numbers of the form are: (Sequence A049536 in OEIS ) ${\displaystyle \operatorname {kgV} (1,\dotsc ,n)+1}$ ${\displaystyle 2,3,7,13,61,421,2521,232792561,\dotsc }$

After the Dirichlet prime number set contains an arithmetic sequence (wherein , prime and are the natural numbers passes) infinitely many primes (but also composite numbers). However, there are Ben Green and Terence Tao for each arithmetic sequences (determined by ) the primes for delivering successive values. For example: ${\displaystyle a\cdot m+b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle a,b}$ ${\displaystyle k}$

${\displaystyle 43142746595714191+5283234035979900\cdot k}$

Prime numbers for . The method corresponds to the case of linear polynomials. ${\displaystyle k=0,\dotsc ,25}$

Trivial generator

A trivial prime number generator can be inductively defined as follows:

1. ${\displaystyle f(1)=2}$
2. ${\displaystyle f(2)=3}$
3. for is the prime number following on , where simply all numbers in ascending order are tested for whether they are a prime number. ${\displaystyle n\geq 2}$ ${\displaystyle f(n+1)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)+2}$

However, this method is quite ineffective, since all odd natural numbers have to be tested one after the other. As an alternative, it is possible to use a sieve method , e.g. B. Sieve of Eratosthenes or Sieve of Atkin , to create a long enough list of prime numbers and then to go through this to the desired prime number. Sometimes one first determines quantities similar to prime numbers (near prime numbers ).

Wilson theorem

A not very practical formula for all prime numbers is based on Wilson's theorem . Using the rounding function, the formula is :

${\displaystyle f(n)=\left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor (n-1)+2}$ for natural numbers ${\displaystyle n}$

According to Wilson's theorem, prime is if and only if . It follows that the formula only delivers prime numbers and every prime number except 2 exactly once. Because is prime, so is and . Is not prime, so is and . ${\displaystyle n+1}$ ${\displaystyle n!{\bmod {(}}n+1)=n}$ ${\displaystyle n+1}$ ${\displaystyle \left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor =1}$ ${\displaystyle f(n)=n+1}$ ${\displaystyle n+1}$ ${\displaystyle \left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor =0}$ ${\displaystyle f(n)=2}$

Diophantine sets for prime numbers

After the work on Hilbert's tenth problem, there is a system of finitely many Diophantine equations (polynomials over the whole numbers) that have all prime numbers and only these as a solution. According to Yuri Wladimirowitsch Matijassewitsch , there should be such a system with nine or fewer variables. In 1976 James P. Jones and colleagues gave a system of 14 polynomials in 26 variables. The system explicitly consists of the equations:

${\displaystyle \alpha _{0}=wz+h+j-q=0}$

${\displaystyle \alpha _{1}=(gk+2g+k+1)(h+j)+h-z=0}$

${\displaystyle \alpha _{2}=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0}$

${\displaystyle \alpha _{3}=2n+p+q+z-e=0}$

${\displaystyle \alpha _{4}=e^{3}(e+2)(a+1)^{2}+1-o^{2}=0}$

${\displaystyle \alpha _{5}=(a^{2}-1)y^{2}+1-x^{2}=0}$

${\displaystyle \alpha _{6}=16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0}$

${\displaystyle \alpha _{7}=n+\ell +v-y=0}$

${\displaystyle \alpha _{8}=(a^{2}-1)\ell ^{2}+1-m^{2}=0}$

${\displaystyle \alpha _{9}=ai+k+1-\ell -i=0}$

${\displaystyle \alpha _{10}=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0}$

${\displaystyle \alpha _{11}=p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0}$

${\displaystyle \alpha _{12}=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x=0}$

${\displaystyle \alpha _{13}=z+p\ell (a-p)+t(2ap-p^{2}-1)-pm=0}$

with the variables . If and only if there is a solution in natural numbers, the variable is a prime number. ${\displaystyle a,\dotsc ,z}$ ${\displaystyle k+2}$

This can also be summarized in an inequality:

${\displaystyle (k+2)(1-\alpha _{0}^{2}-\alpha _{1}^{2}-\cdots -\alpha _{13}^{2})>0}$

If one substitutes natural numbers for the individual variables, then is a prime number if and only if the inequality is fulfilled. ${\displaystyle k+2}$

There is also a system of Diophantine equations generating the prime numbers (and only these) with only ten variables, but with a very high degree (of the order of magnitude ). According to Thoralf Skolem, one can always find such a system with only polynomials at most fourth degree, but in this case the number of variables is very high (at least 58, as far as known). The methods have so far been of no practical use. ${\displaystyle n}$ ${\displaystyle 10^{45}}$

Mills formula

WH Mills showed in 1947 that there is a real number such that ${\displaystyle A}$

${\displaystyle \left\lfloor d_{n}\right\rfloor =\left\lfloor A^{3^{n}}\right\rfloor }$

is prime for all natural numbers . Assuming the Riemann Hypothesis, one can show that the smallest such (the so-called Mill's constant ) has a value of about . The prime numbers generated by the formula hot Mills primes: , , Since about little known (not even know if the constant is rational or irrational) has the formula but no practical value. ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle 1{,}3063778838630806904686144926\dots }$ ${\displaystyle \left\lfloor d_{1}\right\rfloor =2}$ ${\displaystyle \left\lfloor d_{2}\right\rfloor =11}$ ${\displaystyle \left\lfloor d_{3}\right\rfloor =1361.}$ ${\displaystyle A}$

Wright's formula

EM Wright found a formula similar to Mills' . Wright showed that there is a real number such that ${\displaystyle \alpha }$

${\displaystyle \left\lfloor g_{n}\right\rfloor =\left\lfloor 2^{\dots ^{2^{2^{\alpha }}}}\right\rfloor }$

prim is for everyone . ${\displaystyle n\geq 1}$

The following is defined recursively: ${\displaystyle g_{n}}$

${\displaystyle g_{0}=\alpha }$

${\displaystyle g_{n+1}=2^{g_{n}}}$ For ${\displaystyle n\geq 0}$

Wright also included the first decimal places of . That gives the prime numbers , and . It turns out that with a value of ${\displaystyle \alpha =1{,}9287800\dots }$ ${\displaystyle \alpha }$ ${\displaystyle \left\lfloor g_{1}\right\rfloor =\left\lfloor 2^{\alpha }\right\rfloor =3}$ ${\displaystyle \left\lfloor g_{2}\right\rfloor =13}$ ${\displaystyle \left\lfloor g_{3}\right\rfloor =16381}$ ${\displaystyle \alpha \approx 1{,}9287800}$

${\displaystyle \left\lfloor g_{4}\right\rfloor =\left\lfloor 2^{2^{2^{2^{\alpha }}}}\right\rfloor =19139664204631104...822015417386540}$

(the dots mean 4900 decimal places not shown) is a number with 4932 decimal places, but which is even (that is, not a prime number), that is, this value of must be slightly corrected. Far more decimal places are needed for the following prime numbers. ${\displaystyle \alpha }$

Since the formula is based on knowledge of , it is practically as useless as Mills'. ${\displaystyle \alpha }$

Conway's prime number generator

For the prime number generating machine (PRIMEGAME) by John Horton Conway see FRACTRAN . However, the method is also impractical for generating lists of prime numbers.

Prime number generator for finite sets of prime numbers

Ross Honsberger gives a simple proof of the following theorem:

Divide the first prime numbers arbitrarily into two disjoint sets , so that . Let be the product of the elements of and that of the elements of . may also be empty , then is ( empty product ). If so , then is prime, and is prime if . ${\displaystyle n}$ ${\displaystyle A,B}$ ${\displaystyle A\cup B=\{2,\dotsc ,p_{n}\}}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle a=1}$ ${\displaystyle a+b<p_{n+1}^{2}}$ ${\displaystyle a+b}$ ${\displaystyle |a-b|}$ ${\displaystyle 1<|a-b|<p_{n+1}^{2}}$

Example: (only numbers smaller than are considered ): ${\displaystyle p_{n}=5}$ ${\displaystyle p_{n+1}^{2}=7^{2}=49}$

${\displaystyle 2\cdot 3+5=11,\quad 2\cdot 3-5=1}$

${\displaystyle 2\cdot 5+3=13,\quad 2\cdot 5-3=7}$

${\displaystyle 3\cdot 5+2=17,\quad 3\cdot 5-2=13}$

${\displaystyle 2\cdot 3\cdot 5+1=31,\quad 2\cdot 3\cdot 5-1=29}$

Second example: (only numbers smaller than are considered ): ${\displaystyle p_{n}=11}$ ${\displaystyle p_{n+1}^{2}=13^{2}=169}$

${\displaystyle 2\cdot 11+3\cdot 5\cdot 7=127}$

${\displaystyle 3\cdot 5\cdot 11-2\cdot 7=151}$

However are

${\displaystyle 3\cdot 5+2\cdot 7\cdot 11=169,}$

${\displaystyle 2\cdot 3\cdot 5\cdot 11-7=323}$

not less than 169 and therefore not prime.

Web links

• Eric W. Weisstein : Prime Formulas . In: MathWorld (English).

Individual evidence

1. ↑ Eric W. Weisstein : Green-Tao Theorem . In: MathWorld (English).
2. ↑ James P. Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens: Diophantine representation of the set of prime numbers. American Mathematical Monthly, Vol. 83, 1976, pp. 449-464.
3. ↑ James P. Jones: Universal diophantine equation. Journal of Symbolic Logic, Volume 47, 1982, pp. 549-571.
4. ↑ Mills: A prime-representing function. Bulletin of the AMS, Volume 53, 1947, p. 604.
5. ↑ Follow A051021 in OEIS .
6. ^ EM Wright: A prime-representing function. American Mathematical Monthly, Volume 58, 1951, pp. 616-618.
7. ^ Robert Baillie: Wright's Fourth Prime [1]
8. ^ Richard K. Guy : Conway's Prime Producing Machine. Mathematics Magazine, Volume 56, 1983, pp. 26-33.
9. ^ Honsberger: More Mathematical Morsels. Mathematical Association of America 1991, p. 108 (Morsel 20).