mersenneforum.org > Math Find Mersenne Primes twice as fast?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-14, 20:46 #1 Derived   Apr 2016 210 Posts Find Mersenne Primes twice as fast? 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
2016-05-14, 20:57   #2
CRGreathouse

Aug 2006

5,987 Posts

Hi David!

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

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

2016-05-14, 21:01   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234068 Posts

Hi David,
Yes, of course the search does that. In fact it does more than that. Check The Math web page, second paragraph.
Quote:
 Mersenne numbers are of the simple form 2P-1, where P is the exponent to be tested. It is easy to prove that if 2P-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, 2P-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!)

 2016-05-15, 02:08 #4 Derived   Apr 2016 216 Posts 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!
 2016-09-07, 06:06 #5 devarajkandadai     May 2004 22·79 Posts Mersenne primes 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 ).
2016-09-07, 07:09   #6
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 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?

2016-09-07, 10:46   #7
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,153 Posts

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

Last fiddled with by a1call on 2016-09-07 at 11:01

 2016-09-07, 11:47 #8 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,153 Posts For my last post x and/or m will have to be not 1.
2016-09-07, 14:30   #9
CRGreathouse

Aug 2006

5,987 Posts

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

2016-09-07, 17:16   #10
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,153 Posts

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

Last fiddled with by a1call on 2016-09-07 at 17:18

2016-09-07, 17:24   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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

Last fiddled with by science_man_88 on 2016-09-07 at 17:43

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 10 2018-01-31 19:26 BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37 Andrew Thall GPU Computing 109 2014-07-28 22:14 houding PrimeNet 1 2014-02-24 20:25 Dresdenboy Programming 10 2004-02-29 17:27

All times are UTC. The time now is 13:16.

Wed Dec 7 13:16:42 UTC 2022 up 111 days, 10:45, 0 users, load averages: 0.80, 0.65, 0.74