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

• Nov 20th 2010, 12:28 PM
paulrb
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)
• Nov 20th 2010, 12:55 PM
roninpro
You can use Euclid's proof to generate that new prime. If you have some list of primes $\displaystyle p_1,p_2,\ldots, p_n$, then we consider the number $\displaystyle 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 $\displaystyle p_1=2$ and $\displaystyle p_2=7$, then $\displaystyle p_1p_2+1=15$. This isn't prime, but if we factor it, we have $\displaystyle 15=3\cdot 5$, so we have at least one new prime not on our list.
• Nov 20th 2010, 01:40 PM
paulrb
Oh right...I mean one that doesn't require trial and error factoring though.
• Nov 20th 2010, 01:46 PM
roninpro
• Nov 20th 2010, 02:15 PM
Bingk
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 ...
• Nov 24th 2010, 05:14 PM
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.
• Nov 24th 2010, 06:17 PM
chiph588@
Quote:

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.
• Nov 25th 2010, 04:23 AM
PaulRS
Given the first n primes $\displaystyle p_1,...,p_n$ we have:

$\displaystyle 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 $\displaystyle 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. (Rofl)