mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-08-27, 18:37   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

11100011112 Posts
Default 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 !
T.Rex is offline   Reply With Quote
Old 2015-08-27, 19:02   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

3·31·97 Posts
Default

It is A261539 doubled.
Batalov is offline   Reply With Quote
Old 2015-08-27, 19:16   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
T.Rex is offline   Reply With Quote
Old 2015-08-27, 19:41   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

3×31×97 Posts
Default

You will find: ... 2754, 2757, 3246, ... 6186, 11340, 12885, 84708, 87120 ... (x 2)
Batalov is offline   Reply With Quote
Old 2015-08-27, 20:29   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Yes. I found 12372 = 2*6186 .
T.Rex is offline   Reply With Quote
Old 2015-08-28, 03:14   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

853410 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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
LaurV is offline   Reply With Quote
Old 2015-08-28, 07:00   #7
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16058 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2015-08-28, 07:21   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011000100102 Posts
Default

Quote:
Originally Posted by danaj View Post
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
ATH is offline   Reply With Quote
Old 2015-08-28, 08:09   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

17·53 Posts
Default

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
danaj is offline   Reply With Quote
Old 2015-08-28, 18:33   #10
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by ATH View Post
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 !
T.Rex is offline   Reply With Quote
Old 2015-08-28, 18:39   #11
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

11100011112 Posts
Default

Quote:
Originally Posted by danaj View Post
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 .
T.Rex is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OEIS sequence A027750 MattcAnderson MattcAnderson 2 2017-04-26 22:19
Adding M(37156667) to OEIS lidocorc Information & Answers 1 2016-12-11 07:26
OEIS - A057732 : 2^n + 3 T.Rex Miscellaneous Math 40 2015-09-15 14:01
OEIS - A059242 : 2^n+5 , n odd T.Rex Miscellaneous Math 7 2015-08-28 18:04
my misunderstanding of the OEIS science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 04:29.

Thu May 28 04:29:46 UTC 2020 up 64 days, 2:02, 1 user, load averages: 1.16, 1.37, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.