mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-05-14, 20:46   #1
Derived
 
Apr 2016

2 Posts
Default 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<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.
Derived is offline   Reply With Quote
Old 2016-05-14, 20:57   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,493 Posts
Default

Hi David!

Quote:
Originally Posted by Derived View Post
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 View Post
****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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-14, 21:01   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100011011112 Posts
Default

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!)
Batalov is offline   Reply With Quote
Old 2016-05-15, 02:08   #4
Derived
 
Apr 2016

2 Posts
Default

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!
Derived is offline   Reply With Quote
Old 2016-09-07, 06:06   #5
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

1001111002 Posts
Default 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 ).
devarajkandadai is offline   Reply With Quote
Old 2016-09-07, 07:09   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,493 Posts
Default

Quote:
Originally Posted by devarajkandadai View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2016-09-07, 10:46   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111110000002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
a1call is offline   Reply With Quote
Old 2016-09-07, 11:47   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

198410 Posts
Default

For my last post x and/or m will have to be not 1.
a1call is offline   Reply With Quote
Old 2016-09-07, 14:30   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010101002 Posts
Default

Quote:
Originally Posted by a1call View Post
4^n-1 can only be prime for n=1
Devaraj was talking about prime factors of exponentials, not the exponentials being primes.
CRGreathouse is offline   Reply With Quote
Old 2016-09-07, 17:16   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26×31 Posts
Default

Quote:
Originally Posted by devarajkandadai View Post
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
a1call is offline   Reply With Quote
Old 2016-09-07, 17:24   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
method to find primes (in a certain form) Alberico Lepore Alberico Lepore 10 2018-01-31 19:26
Fast modular reduction for primes < 512 bits? BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37
Fast Mersenne Testing on the GPU using CUDA Andrew Thall GPU Computing 109 2014-07-28 22:14
DC chance to find Mersenne Prime houding PrimeNet 1 2014-02-24 20:25
Fast calculations modulo small mersenne primes like M61 Dresdenboy Programming 10 2004-02-29 17:27

All times are UTC. The time now is 09:25.

Sat Feb 27 09:25:23 UTC 2021 up 86 days, 5:36, 0 users, load averages: 1.61, 1.57, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.