20141209, 23:49  #12 
Dec 2014
2^{2}·5 Posts 
but it also said 11 wasn't prime, so just forget about all these posts... just ignore me

20141209, 23:52  #13 
Dec 2014
2^{2}·5 Posts 
@minigeek! thank you, my computer science friend sent me this code (passing the blame on her) and she commented it wrong, which is why I was getting confused. thank you

20141209, 23:59  #14  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:
I think I see something else that makes me think the pseudocode goes from S(0) to S(p2) and mathgirls code goes from s(0) to s(p1) ? 

20141210, 00:02  #15  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
There's nothing wrong with thrashing around a bit when learning coding (or even much, much later sometimes)
Here are the intermediate values when checking if 2^{7}  1 is prime, using the LL test: http://www.mersenne.org/various/math.php#lucaslehmer Quote:
Last fiddled with by only_human on 20141210 at 00:25 Reason: I messed up too. not 7. 127 

20141210, 00:50  #16 
Dec 2014
2^{2}×5 Posts 
I will look into how to write a better one tomorrow then, I really I hope I can get it all done by thrusday! in python, if you put the range(1, n) it actually goes, from 1 to (n1). So I think my code goes from 1 to p1 so that means it will actually go to 1 to p2. Thanks for all your help guys (though correct me if I'm wrong!)

20141210, 00:51  #17 
"Gang aft agley"
Sep 2002
2·1,877 Posts 
So a confusing element here is that Mersenne primes in the form 2^{p}  1 must have a prime exponent otherwise the number is composite, but that p is not the prime being tested. The number being tested for primality is 2^{p}  1.
Even on this forum we mess around with terminology and might talk about a Mersenne prime sometimes referring to the exponent, sometimes the entire number, and sometimes referring to the ordinal number from a list of known Mersenne primes. Last fiddled with by only_human on 20141210 at 00:55 
20141210, 03:28  #18  
May 2013
East. Always East.
11×157 Posts 
The first issue I can see is you're confusing P with M_{P} = 2^{P}  1. You're trying to prove the primality of M_{P}, not P.
For example, if you run P = 8191, you're testing the primality of M_{8191} = 2^{8191}  1 =~ 5.454 x 10^{2465}, but your output is commenting on the primality of 8191 which is wrong. The second issue is you're going from i = 1 to i = P  1, which is one too many. You want P  2 iterations, not P  1. With the above example, you're using 8089 iterations to check that 2465digit number. You don't run M_{P}  2 iterations, You run P  2 iterations. Quote:
Saying M57,885,161 is shorthand for saying M_{57,885,161} because we're too lazy to put the subscript tags every time we refer to a number. It gets confusing because M_{57,885,161} = M48, currently, because we also use that notation to refer to the Mersenne Primes by rank, where M48 is the 48th Mersenne Prime currently known. Eventually, M127 is going to mean two different things unless we specify: either M_{127} (= 2^{127}  1) or the 127th Mersenne Prime. For now, that's not an issue. More confusing yet is the fact that we'll sometimes skip the M bit and just say something like: "I'm going to do ECM on the 300,000 to 400,000 range" which could be referring to the exponents or to the number itself, although we exceedingly rarely refer to Mersenne Numbers by their actual numbers because even the "tiny" ones are too big. The worst part is when we refer to 100million digit Mersennes and talk about the 100M range. I always make sure to say the 100M digits range, but some people don't, or they forget. So 100M could mean 100million digit mersennes OR the M_{100,000,000} range. Yup. Confusing. Last fiddled with by TheMawn on 20141210 at 03:47 Reason: Looks like we're okay now. 

20141210, 06:50  #19  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
As for complexity, continuing on from what TheMawn about the LL test here, each inner loop of the algorithm needs a squaring, a subtraction and (effectively benefits from) a mod operation.
This link points to Wikipedia's LL Test Time complexity Because Mersenne numbers are one less than a power of two, calculating within the modulus of a Mersenne number can be quite cheap computationally. Setting that aside for now, the big part of the inner loop complexity is the squaring operation. I'm not conversant in what is being done here. Fast multiplication for large numbers use FFTs or similar to do convolutions for multiplication. I believe in particular the IBDWT avoids needing zero padding and perhaps the mod operation ends up being essentially free too. I am absolutely ignorant in this area so will stop there. Going slightly offtopic to mention something to forum members: Just to show that reviewing what we think we know is nice, I was was unaware of this on that Wikipedia page linked to above: Quote:
Quote:
Last fiddled with by only_human on 20141210 at 06:53 

20141210, 07:48  #20  
Aug 2006
5,987 Posts 
Quote:
Fürer's algorithm is actually really nice because it takes an existing algorithm and improves it slightly, but also making it easier (IMO) to understand. 

20141210, 09:31  #21 
Dec 2014
2^{2}×5 Posts 
so my code to find mersenne primes (not this code I am showing you now!) finds the M_p and the corresponding p and returns a separate list of both. If I were to iterate through the list of p and use the LL test on them and instead make it return 2**p  1. then it will work.
and what's soo cool about it is that my code can only return 8 mersenne primes, where as this one can return moreee because it is only finding the correct p, which is a lot smaller than m so my computer can handle it.! if that is all correct! that is awesome 
20141210, 14:06  #22 
Dec 2014
Sydney, Australia
2 Posts 
Code:
and what's soo cool about it is that my code can only return 8 mersenne primes, where as this one can return moreee because it is only finding the correct p, which is a lot smaller than m so my computer can handle it.! if that is all correct! that is awesome Which 8 Mersenne primes can your computer return only? The first 8 ones? 2^{2}1, 2^{3}1, 2^{5}1, 2^{7}1, 2^{13}1, 2^{17}1, 2^{19}1, 2^{31}1 ????? If you really find the code to calculate the correct p for newrecord Mersenne primes, then you just made GIMPS redundant But I am pretty much sure u didn´t ! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 