Find Mersenne Primes twice as fast?

[Derived]

Greetings. My name is David Moss. I am currently 17 years old. I would greatly appreciate a response to this thread as it may greatly improve the rate of finding Mersenne primes.

So recently I got interested in finding the pattern for prime numbers like many users probably have. As I was looking at some number patterns, I have found enough information to prove that the "p" in 2^p-1 can never under ANY circumstance be even. Here is an example of why this might be important:

In a given set (Note: < represents equal to or less than) of 1<p<100, there are only 100 possible numbers following the form 2^p-1. Since I proved that Mersenne primes cannot be even, then only 50 numbers have the potential to be prime. In other words, when searching for the next Mersenne prime, you can skip all the p=even to increase the search speed by twice as much.

****So my question is, does the GIMPS program skip even numbers for "p" or does it calculate odd and even values for "p". If it searches both, then searching only odd numbers for "p" will greatly improve the efficiency of this search for merseynne primes.

I would (hopefully) assume that this is already being done but who knows. If my proof is needed, I would gladly post it on here. It is quite cool if I do say so myself and am currently trying to use a similar method for other proofs for prime finding.

[CRGreathouse]

Hi David!

Originally Posted by Derived

So recently I got interested in finding the pattern for prime numbers like many users probably have. As I was looking at some number patterns, I have found enough information to prove that the "p" in 2^p-1 can never under ANY circumstance be even.

Correct! In fact, you can say more: if p = mn, then 2^m - 1 and 2^n - 1 both divide 2^p - 1, so p must be a prime number.

Originally Posted by Derived

****So my question is, does the GIMPS program skip even numbers for "p" or does it calculate odd and even values for "p". If it searches both, then searching only odd numbers for "p" will greatly improve the efficiency of this search for merseynne primes.

Yes, GIMPS skips even exponents, odd composite exponents, and exponents which generate numbers with small prime factors. Only numbers that pass all of these get the full Lucas-Lehmer testing.

[Batalov]

Hi David,
Yes, of course the search does that. In fact it does more than that. Check The Math web page, second paragraph.

Mersenne numbers are of the simple form 2^P-1, where P is the exponent to be tested. It is easy to prove that if 2^P-1 is prime, then P must be a prime. Thus, the first step in the search is to create a list of prime exponents to test.

Look back at your own argument. You already saw that P cannot be even (or if we were inclined to nitpick, even P>2), because if P were even, 2^P-1 would have been a difference of squares and therefore composite. But now, make the next step: can P be a multiple of 3? Hint: no! 2[SUP]P[/SUP]-1 would have been a difference of cubes and therefore composite. What about a multiple of 5? and so on, and you end up with the sieve of Eratosthenes.

...(and there we have it, Charles was even faster to respond!)

[Derived]

Thank you both for the fast and helpful responses. I read more into how the software worked, and now I really appreciate the practicality side of it. Before I found GIMPS, I focused more on the twin prime numbers as opposed to mersenne because I thought these numbers in particular would have special properties. I quickly realized of course that it is not that easy, especially searching for numbers exceeding 1 million digits. These algorithms just made me realize how well thought out this process is and why mersenne primes in particular are useful. Well thanks again; you guys just made math all the more awesome for me!

[devarajkandadai]

Incidentally the only exponential function that generates all the odd primes is 2^n-1.All other exponential functions such as 3^n-2 are such that there are sequences of impossible prime factors (see A123239 on OEIS ).

[CRGreathouse]

Originally Posted by devarajkandadai

Incidentally the only exponential function that generates all the odd primes is 2^n-1.All other exponential functions such as 3^n-2 are such that there are sequences of impossible prime factors (see A123239 on OEIS ).

Is that really true? I mean, clearly you can't use any primes dividing the base (hence "odd primes" above), but other than that it seems that there are plenty of exponential functions that work just fine. And even if you want to be a stickler about having each odd prime (rather than more generously allowing finitely many exceptions) you can always use things like 4^n - 1.

But if you allow skipping 3 in place of 2 for 3^n - 1, doesn't that work for all remaining primes?

[a1call]

Originally Posted by CRGreathouse

Is that really true? I mean, clearly you can't use any primes dividing the base (hence "odd primes" above), but other than that it seems that there are plenty of exponential functions that work just fine. And even if you want to be a stickler about having each odd prime (rather than more generously allowing finitely many exceptions) you can always use things like 4^n - 1.

But if you allow skipping 3 in place of 2 for 3^n - 1, doesn't that work for all remaining primes?

4^n-1 can only be prime for n=1,
However 4^n-3 would give primes more often, but never Mersenne primes.
For 2^(xn)-m, m could be chosen to equate a Mersenne number or Mersenne prime only once per m.

[a1call]

For my last post x and/or m will have to be not 1.

[CRGreathouse]

Originally Posted by a1call

4^n-1 can only be prime for n=1

Devaraj was talking about prime factors of exponentials, not the exponentials being primes.

[a1call]

Originally Posted by devarajkandadai

Incidentally the only exponential function that generates all the odd primes is 2^n-1.All other exponential functions such as 3^n-2 are such that there are sequences of impossible prime factors (see A123239 on OEIS ).

2^n-1 does not generate all the of odd primes. It does not generate 3,5,11,13,...
2n-1 generates all the odd prime numbers as well as all the other odd numbers.
3^n-2 is prime for n=2,4,...
4^n-1 is always divisible by 3 and is only prime for n=1.

[science_man_88]

Originally Posted by a1call

2^n-1 does not generate all the of odd primes. It does not generate 3,5,11,13,...
2n-1 generates all the odd prime numbers as well as all the other odd numbers.
3^n-2 is prime for n=2,4,...
4^n-1 is always divisible by 3 and is only prime for n=1.

2^n-1 has a divisor of 3 for all even exponents and a divisor of 5 for all multiple of 4 exponents. in fact if a prime p divides a polynomial (or other expression in theory) it must divide within the first p integer terms of course we have that for prime p 2^(p-1)-1 is divisible by p as well as all of the exponents that are multiples of p-1.