20160514, 20:46  #1 
Apr 2016
2_{10} 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^p1 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^p1. 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. 
20160514, 20:57  #2  
Aug 2006
5,987 Posts 
Hi David!
Quote:
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 LucasLehmer testing. 

20160514, 21:01  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23406_{8} 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:
...(and there we have it, Charles was even faster to respond!) 

20160515, 02:08  #4 
Apr 2016
2_{16} 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!

20160907, 06:06  #5 
May 2004
2^{2}·79 Posts 
Mersenne primes
Incidentally the only exponential function that generates all the odd primes is 2^n1.All other exponential functions such as 3^n2 are such that there are sequences of impossible prime factors (see A123239 on OEIS ).

20160907, 07:09  #6  
Aug 2006
5,987 Posts 
Quote:
But if you allow skipping 3 in place of 2 for 3^n  1, doesn't that work for all remaining primes? 

20160907, 10:46  #7  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
Quote:
However 4^n3 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 20160907 at 11:01 

20160907, 11:47  #8 
"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.

20160907, 14:30  #9 
Aug 2006
5,987 Posts 

20160907, 17:16  #10  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,153 Posts 
Quote:
2n1 generates all the odd prime numbers as well as all the other odd numbers. 3^n2 is prime for n=2,4,... 4^n1 is always divisible by 3 and is only prime for n=1. Last fiddled with by a1call on 20160907 at 17:18 

20160907, 17:24  #11 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
2^n1 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^(p1)1 is divisible by p as well as all of the exponents that are multiples of p1.
Last fiddled with by science_man_88 on 20160907 at 17:43 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
method to find primes (in a certain form)  Alberico Lepore  Alberico Lepore  10  20180131 19:26 
Fast modular reduction for primes < 512 bits?  BenR  Computer Science & Computational Number Theory  2  20160327 00:37 
Fast Mersenne Testing on the GPU using CUDA  Andrew Thall  GPU Computing  109  20140728 22:14 
DC chance to find Mersenne Prime  houding  PrimeNet  1  20140224 20:25 
Fast calculations modulo small mersenne primes like M61  Dresdenboy  Programming  10  20040229 17:27 