Given the first n primes, is there a known function that always produces a new prime?

**paulrb** · November 20th 2010, 12:28 PM

When I first read Euclid's proof that there are infinite primes, I mistakenly thought the product of all n primes plus 1 must also be prime. That is not true. However, are there any other known formulas that can use some or all of the first n primes and be guaranteed to produce a new prime that is not one of the first n? (but not necessarily the n+1th prime)

**roninpro** · November 20th 2010, 12:55 PM

You can use Euclid's proof to generate that new prime. If you have some list of primes $p_1,p_2,\ldots, p_n$ , then we consider the number $p_1p_2\cdots p_n+1$ . Although this number may not be prime, you can factor it to get a new prime not on your list.

For example, if we have $p_1=2$ and $p_2=7$ , then $p_1p_2+1=15$ . This isn't prime, but if we factor it, we have $15=3\cdot 5$ , so we have at least one new prime not on our list.

**paulrb** · November 20th 2010, 01:40 PM

Oh right...I mean one that doesn't require trial and error factoring though.

**roninpro** · November 20th 2010, 01:46 PM

Try Wikipedia:

Formula for primes - Wikipedia, the free encyclopedia

**Bingk** · November 20th 2010, 02:15 PM

Not exactly an answer, I started this thread http://www.mathhelpforum.com/math-help/f7/regarding-wilsons-theorem-150928.html
some time ago, just something I observed.

In summary, given a prime p, check if ( (p-1)! + 1 ) / p is also prime. If it's not, divide by p again. That should be prime. It works up to p = 101. After that, there's problems with doing the large factorial ...

**browni3141** · November 24th 2010, 05:14 PM

I wouldn't even bother with using Wilson's Theorom for practical purposes. It's interesting to study, but it's probably faster to check each prime up to sqrt(n) as a divisor of n, n being the number you are testing. This is probably the easiest method to write a program for. There are prime generating polynomials, but they aren't perfect. This one discovered by Euler is considered best:
x*x - x + 41

I'm pretty sure that there is no formula like the one you are asking for though.

**chiph588@** · November 24th 2010, 06:17 PM

Originally Posted by browni3141

I wouldn't even bother with using Wilson's Theorom for practical purposes. It's interesting to study, but it's probably faster to check each prime up to sqrt(n) as a divisor of n, n being the number you are testing. This is probably the easiest method to write a program for. There are prime generating polynomials, but they aren't perfect. This one discovered by Euler is considered best:
x*x - x + 41

I'm pretty sure that there is no formula like the one you are asking for though.

It can be proven that there are no trivial prime polynomials.

**PaulRS** · November 25th 2010, 04:23 AM

Given the first n primes $p_1,...,p_n$ we have:

$p_{n+1}=\left \lfloor 1 - \log_2\left(-\tfrac{1}{2}+\displaystyle\sum_{d|P_n}{\displaysty le\frac{\mu(d)}{2^d-1}}\right) \right \rfloor$ where $P_n = p_1\cdot ...\cdot p_n$ is the product of the first n primes.

You can see the proof here.

But I would rather use some brute primality testing if I had to find the next prime, hahaha.

Thread: Given the first n primes, is there a known function that always produces a new prime?

LinkBack

Thread Tools

Display

Given the first n primes, is there a known function that always produces a new prime?

Similar Math Help Forum Discussions

Primes that are quadratic residues another prime.

Twins of primes with one distinct prime factor

[SOLVED] Prove that an isomorphism produces a basis of W

Prime gaps between primes

What is wrong with these operations? My calculator produces a different answer

Search Tags