Finding large prime numbers?

Question

It is probably a useful method for finding large prime numbers and even more useful for
identifying the sequence of prime numbers in areas where thesequence of primes isn't known
(since the numbers are so big).

Consider the product 2*3*5*7*11.....p ie the product of all primes from to 2 to some prime
number p.

If q is a prime greater than p, than why is it likely that 2*3*5...p + q = a prime number.

For example consider the product 2*3*5*7=210. And let us consider the consecutive prime
numbers 11,13,17,19,23,29 and 31. We get

210+11=221
210+13=223
210+17=227
210+19=229
210+23=233
210+29=239
210+31=241

Notice that all of these numbers are prime except for 221. We can do a similar experiment
with say 2*3*5*7*11=2310, except this time use the primes 13,17,19,23,29,31,37

2310+13=2323
2310+17=2327
2310+19=2329
2310+23=2333
2310+29=2339
2310+31=2341
2310+37=2347

In this instance were not so lucky in that we only have 2333, 2339, 2341 and 2347 being
prime. Obviously this method gets worse the higher you go up. However what makes this
procedure useful, is that it enables you to determine consecutive prime numbers (this is
why you may have noticed that there are no prime numbers between the four primes written
above, or in the six primes in the first example).

Anyone here would like take a stab at why we get these results ?

Answer 1

The product of all primes not exceeding a prime p is called the "primorial" of p and is usually denoted p#.

The reason why the number N = p#+q (when q is either 1 or a prime greater than p) is more likely to be a prime than a random number of the same size is simply that N can only have prime divisors that are greater than p (that's easy to prove).

Loosely speaking the probability that a random number N is prime is 1/ln(N). That's a way of stating the so-called "prime number theorem".

On the other hand, the numbers which are multiples of p have density 1/p (in a sense which could be made precise, the probability that a random number is multiple of p is just 1/p). Conversely, a random number is not a multiple of p with probability (1-1/p). If p1 and p1 are coprime (in particular, if they're both prime) then the probability of being divisible neither by p1 nor by p2 is (1-1/p1)(1-1/p2).

For a prime p, the probability that a random number does not have any prime factor less than or equal to p is: K=(1-1/2)(1-1/3)(1-1/5)...(1-1/p). K is 1/2 for p=2, it's 1/3 for p=3, it's 4/15 for p=5, it's 8/35 for p=7. it's 16/77 for p=11, etc.

Now, heuristically, your number N=p#+q will be prime with probability 1/(K*ln(N)). For p=11, this would be about 77/16 = 4.8125 more likely than a random N of the same size.

To get an idea of the numbers involved and understand how the "trick" becomes worse and worse for large numbers, you may compute the above expression for N=p#+1
using various values of p (this is a good indication of the probability that p#+q is prime if q is a prime between p+1 and a small fraction of p#). For p=7, you would obtain 0.818199... So, you could expect a prime for about 82% of the "small" values of q (well below 2*3*5*7 = 210). Of course, in this case, the allowed range of q is so small that statistics do not mean much. Similarly, you get about 62.1% for p=11, 50.6% for p=13, 42.1% for p=17, 36.3% for p=19, etc.

Actually, the p#+q "trick" is more commonly used the other way around to give explicitely a sequence of p-1 consecutive numbers WITHOUT a single prime in them. Namely:

p#+2, p#+3, p#+4, p#+5, p#+6, .. ... p#+p-1, p#+p

Answer 2

These results are not as surprising as you think they are.

The number N = 2*3*5*7*...*p + q, where p is a prime and q is a larger prime, cannot be divisible by any prime up to and including p. This means that, from all the numbers around N, a large proportion of the composite numbers are impossible, so the primes form a relatively larger proportion of the possible results. This applies also to N = 2*3*5*...*p - q, and when q is 1 instead of a larger prime.

Your second point is just an example of the so-called "wheel based" methods of stepping through possible primes, which can be made to work anywhere, not just near 2*3*5*...*p.

Methods of generating prime numbers for computer security procedures already have much better ways than this of stacking the odds in their favour.

But don't be discouraged! Keep investigating and exploring, but keep checking the known literature too. Chris Caldwell's Prime Pages are one of the best resources on the net for this.

Answer 3

I am not sure if you are familiar with it but you are talking about something very similar to the classical proof of infiniteness of the prime numbers set. Euclid argued that if there were finitely many primes, say, P1,...., Pn, then
N = (P1) (P2)...(Pn)+1
would be a number not divisible by any of the primes in our list: P1,...,Pn. However this does not necessarily mean if you take the first n primes, (P1)...(Pn)+1 will also be prime, because it can still be divisible by another smaller prime not among P1,...,Pn. In your method you replace +1 term with +q term which is effectively the same thing and you observe the likelyhood of primeness is high. When the numbers are small like 2, 3, 5, 7 there is nothing too suprizing about it as there are not many prime numbers between the highest prime we used "7" and (P1) ... (Pn)+q. So my guess is the phenomenon you observed will rapidly disappear if you try the product of, say 10-15 prime numbers. This is of course only a guess. However, to find very large primes, most people in this field would try things like Mersenne numbers (numbers of the form 2^(2^p)-1, where p is prime) rather than products like yours.

Answer 4

Have you been reading Marcus du Sautoy's book? (If not, I'd recommend it, it's called Music of the Primes)

It's an interesting question, seeing as how nature seems to depend on prime numbers in different cases, but the occurances of them appear to be random. There doesn't seem to be an obvious answer, though there is some kind of harmonic equivalent.