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

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

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)

2. 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.

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

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 ...

5. 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.

6. 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.

7. 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.