OEIS - 2·A261539: (2^n+5)/3 , n even

[T.Rex]

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:

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 !

[Batalov]

It is A261539 doubled.

[T.Rex]

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.

[Batalov]

You will find: ... 2754, 2757, 3246, ... 6186, 11340, 12885, 84708, 87120 ... (x 2)

[T.Rex]

Yes. I found 12372 = 2*6186 .

[LaurV]

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...)

[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. 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.

[ATH]

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).

[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.

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.

[T.Rex]

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 !

[T.Rex]

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 .