mersenneforum.org OEIS - 2·A261539: (2^n+5)/3 , n even
 Register FAQ Search Today's Posts Mark Forums Read

 2015-08-27, 18:37 #1 T.Rex     Feb 2004 France 2·457 Posts OEIS - 2·A261539: (2^n+5)/3 , n even This is a new entry to OEIS I have to create I think. The LLT-like 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, n-1, x=Mod(x^2-2,N)) ; if(x==4, print(n," Prime"))) It works fine for n = 2, 4, 6, 12, 18, 24, 42, 84, 300, 390, 780, 822 , that I checked with isprime() before and are 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 LLT-like algorithm that could lead, when using fast implementation of LLT, to new BIG PRPs !
 2015-08-27, 19:02 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33×73 Posts It is A261539 doubled.
2015-08-27, 19:16   #3
T.Rex

Feb 2004
France

2·457 Posts

Quote:
 Originally Posted by Batalov It is A261539 doubled.
Oh Yes ! It is the same series in fact ! Thanks !
I'll probably be able to add some value to it soon.

 2015-08-27, 19:41 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33×73 Posts You will find: ... 2754, 2757, 3246, ... 6186, 11340, 12885, 84708, 87120 ... (x 2)
 2015-08-27, 20:29 #5 T.Rex     Feb 2004 France 2·457 Posts Yes. I found 12372 = 2*6186 .
2015-08-28, 03:14   #6
LaurV
Romulan Interpreter

Jun 2011
Thailand

2×3×52×61 Posts

Quote:
 Originally Posted by T.Rex Yes. I found 12372 = 2*6186 .
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 2015-08-28 at 03:15

 2015-08-28, 07:00 #7 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 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 M-R test would be faster as well, so I don't see this helping. - for fun and enlightenment.
2015-08-28, 07:21   #8
ATH
Einyen

Dec 2003
Denmark

3×17×59 Posts

Quote:
 Originally Posted by danaj 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.
It seems pretty obvious to me (assuming I understand it correctly): He just came up with these new LLT algorithms like the Vrba-Reix algorithm he and Anton Vrba found some years back for Wagstaff numbers which is implemented in LLR and he wants to do some initials tests to see if they seem correct or if we can easily find false positives. Even if we do not find any counter examples they will still only be PRP tests for now but maybe they will seem more "trustworthy" than a simple MR test, since they are based of the LL/LLR test.

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 2015-08-28 at 07:22

 2015-08-28, 08:09 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38A16 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 as-is ("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 L-L 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 2015-08-28 at 08:12
2015-08-28, 18:33   #10
T.Rex

Feb 2004
France

2·457 Posts

Quote:
 Originally Posted by ATH It seems pretty obvious to me (assuming I understand it correctly): He just came up with these new LLT algorithms like the Vrba-Reix algorithm he and Anton Vrba found some years back for Wagstaff numbers which is implemented in LLR and he wants to do some initials tests to see if they seem correct or if we can easily find false positives. Even if we do not find any counter examples they will still only be PRP tests for now but maybe they will seem more "trustworthy" than a simple MR test, since they are based of the LL/LLR test. 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).
Well ! Exactly what I mean. Thanks !

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 Vrba-Reix algorithm.
At least, it is fun !

2015-08-28, 18:39   #11
T.Rex

Feb 2004
France

2·457 Posts

Quote:
 Originally Posted by danaj 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. ... Edit: just wanted to say an extra thanks to T.Rex for the method explanation on the 2^n+3 thread.
Thanks !
Jean Penné implemented the Reix-Vrba algorithm for Wagstaff numbers (use of a LLT-like 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^n-3. A050414 .

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 2 2017-04-26 22:19 lidocorc Information & Answers 1 2016-12-11 07:26 T.Rex Miscellaneous Math 40 2015-09-15 14:01 T.Rex Miscellaneous Math 7 2015-08-28 18:04 science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 08:01.

Thu Jan 21 08:01:57 UTC 2021 up 49 days, 4:13, 0 users, load averages: 3.12, 2.53, 2.33