20150827, 18:37  #1 
Feb 2004
France
911 Posts 
OEIS  2·A261539: (2^n+5)/3 , n even
This is a new entry to OEIS I have to create I think.
The LLTlike algorithm, based on a cycle, with classic seed S0=4, is described by this PARI/gp program: Code:
for(i=1, 10000, n=2*i ; N=(2^n+5)/3 ; x=4 ; for(j=1, n1, x=Mod(x^22,N)) ; if(x==4, print(n," Prime"))) I also found: 2430, 5508, 5514, 6492, which are PRP up to now, and more to come. To be checked asap. Please help checking that the algorithm still produces good results with higher values of n. So, here is a new LLTlike algorithm that could lead, when using fast implementation of LLT, to new BIG PRPs ! 
20150827, 19:41  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21570_{8} Posts 
You will find: ... 2754, 2757, 3246, ... 6186, 11340, 12885, 84708, 87120 ... (x 2)

20150827, 20:29  #5 
Feb 2004
France
911 Posts 
Yes. I found 12372 = 2*6186 .

20150828, 03:14  #6 
Romulan Interpreter
Jun 2011
Thailand
5·11·157 Posts 
Are you sure? (hehe, it reminds me when I was kid and I discovered, looking to my hands, that 2*5 is 10, hehe...)
Last fiddled with by LaurV on 20150828 at 03:15 
20150828, 07:00  #7 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
I'm missing something. Using ispseudoprime seems quite a bit faster, and there are faster implementations of that as well. If I add similar pretests (trial division) to this test instead of using BPSW, then I get pretty similar times. Is the point:
 proof pending so the results are definitive primes rather than PRPs. That would certainly make it worthwhile, but I'm inferring that isn't the case.  assumed to be faster with faster infrastructure. The Fermat or MR test would be faster as well, so I don't see this helping.  for fun and enlightenment. 
20150828, 07:21  #8  
Einyen
Dec 2003
Denmark
2^{2}×7×103 Posts 
Quote:
Some day someone might find a way to prove they are actually a fast primality test like the LL test, but the first step is to test if they work at all (since no one has any ideas for working out the proof atm). Last fiddled with by ATH on 20150828 at 07:22 

20150828, 08:09  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
902_{10} Posts 
Thanks ATH, that is helpful. I am happy to see the algorithms, and I get the part about testing. I also see that there is a possibility that the method could be proven in the future.
Comments like "using fast implementation of LLT, to new BIG PRPs !" and "the fastest math ways for proving that a number N is Prime or PRP" confuse me. What does it mean to prove a number is PRP? I went through all three threads more carefully and the first posts are more clear  they just wandered into performance testing very quickly, which seems premature when still testing small inputs for counterexamples. Especially when the code being tested ignores compositeness tests, which is the main source of speed difference. I could also just be reading more into the performance aspect than was intended. It's hard to tell sometimes (for me) if people are proposing a new faster solution asis ("this Pari code is a faster way to generate the sequence!") or a new idea ("this code illustrates my research direction"). Given these aren't Mersenne numbers so we can't do crazy fast mods, would a LL type test be faster than a Fermat test ala PFGW, assuming reasonably similar infrastructure (e.g. both in GMP or both in gwnum)? For this question, just performance  ignore any apples vs. oranges of the perceived or actual correctness of the result. Edit: just wanted to say an extra thanks to T.Rex for the method explanation on the 2^n+3 thread. Last fiddled with by danaj on 20150828 at 08:12 
20150828, 18:33  #10  
Feb 2004
France
1110001111_{2} Posts 
Quote:
Yes. the idea is to show that LLT algorithm works for much more numbers than Fermat and Mersennes. And maybe some day somenone will be able to find a proof. And maybe someone can implement the test like Pené did for VrbaReix algorithm. At least, it is fun ! 

20150828, 18:39  #11  
Feb 2004
France
1617_{8} Posts 
Quote:
Jean Penné implemented the ReixVrba algorithm for Wagstaff numbers (use of a LLTlike algorithm with cycle) in the GIMPS tool. It seems to be very fast. However, I do not master all the details about performance improvements... and I forgot many things these last years. Now, I will open a new thread for 2^n3. A050414 . 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
OEIS sequence A027750  MattcAnderson  MattcAnderson  2  20170426 22:19 
Adding M(37156667) to OEIS  lidocorc  Information & Answers  1  20161211 07:26 
OEIS  A057732 : 2^n + 3  T.Rex  Miscellaneous Math  40  20150915 14:01 
OEIS  A059242 : 2^n+5 , n odd  T.Rex  Miscellaneous Math  7  20150828 18:04 
my misunderstanding of the OEIS  science_man_88  Miscellaneous Math  11  20110518 15:04 