OEIS - A059242 : 2^n+5 , n odd

[T.Rex]

See: https://oeis.org/A059242 .

The LLT-like algorithm, base on a cycle, is described by this PARI/gp program:

for(i=1,100000, n=2*i+1 ; N=2^n+5 ; x=194 ; for(j=1, n-2, x=Mod(x^2-2,N)) ; if(x==194, print(n," Prime") ) )

It works fine for: 3, 5, 11, 47, 53, 141, 143, 191, 273, 341 . There is a gap till 16541, that should be reached by tomorrow.
Please help checking that the algorithm still produces good results with higher values of n.

No false positive, no false negative. Up to now, it is perfect !

So, here is a new LLT-like algorithm that could lead, when using fast implementation of LLT, to new BIG PRPs !

[science_man_88]

Originally Posted by T.Rex

See: https://oeis.org/A059242 .

Th LLT-like algorithm, base on a cycle, is described by this PARI/gp program:

for(i=1,100000, n=2*i+1 ; N=2^n+5 ; x=194 ; for(j=1, n-2, x=Mod(x^2-2,N)) ; if(x==194, print(n," Prime") ) )

It works fine for: 3, 5, 11, 47, 53, 141, 143, 191, 273, 341 . There is a gap till 16541, that should be reached by tomorrow.
Please help checking that the algorithm still produces good results with higher values of n.

No false positive, no false negative. Up to now, it is perfect !

So, here is a new LLT-like algorithm that could lead, when using fast implementation of LLT, to new BIG PRPs !

a=[];forstep(i=100000,1,-1,n=i<<1+1;N=1<<n+5;x=Mod(194,N);forstep(j=n,3,-1,x=sqr(x)-2);if(x==194,a=concat(a,n)));print(a",prime")

should be faster in the code part of it.

[T.Rex]

Originally Posted by science_man_88

a=[];forstep(i=100000,1,-1,n=i<<1+1;N=1<<n+5;x=Mod(194,N);forstep(j=n,3,-1,x=sqr(x)-2);if(x==194,a=concat(a,n)));print(a",prime")

should be faster in the code part of it.

Hummmm That shows nothing on my old Pari/gp on Windows. Should I update it ?

[science_man_88]

Originally Posted by T.Rex

Hummmm That shows nothing on my old Pari/gp on Windows. Should I update it ?

it doesn't print until the end that's one part you can change back to check it. or just lower the high i value it starts with.

(13:12) gp > a=[];forstep(i=1183,1,-1,n=i<<1+1;N=1<<n+3;x=Mod(14,N);forstep(j=n,2,-1,x=sqr(x)-2);if(x==14,a=concat(a,n)));print(a",prime")
[2367, 2191, 2139, 67, 55, 15, 7, 3],prime
(14:36) gp > ##
  ***   last result computed in 3,088 ms.
(14:36) gp > for(i=1,1183,n=2*i+1;N=2^n+3;x=14;for(j=1,n-1,x=Mod(x^2-2,N));if(x==14,print(n," Prime")))
3 Prime
7 Prime
15 Prime
55 Prime
67 Prime
2139 Prime
2191 Prime
2367 Prime
(14:36) gp > ##
  ***   last result computed in 3,220 ms.

is a comparison form your older codes in the other thread(s) though I did a loop outside them to check using 100 times completing the task to my mark and it only resulted in a small savings of 20 seconds ( the 100 rounds of it aka about 200 ms per time it ran up to these limits) I think. edit2: admittedly this is on a machine with windows 10 and version 2.7.4 64 bit version.

[T.Rex]

OK. My PARI/gp code found 16541, which also is in A059242.
It is not useful to let PARI/gp continue searching, since a much faster implementation of LLT must be used in order to find a n greater than 282203 such that N=2^n+5 is a biggest PRP .

I remind people that LLT-like algorithms are the fastest math ways for proving that a number N is Prime or PRP., when such an algorithm has been found by experiment (PRP, like for Wagstaff numbers) or proven (Prime, like for Mersenne or Fermat numbers). But one has to adapt existing LLT-code to the specific number N.

[ATH]

The test is positive for 11, 47, 53, 141, 143, 191, 273, 341, 16541, 34001, 34763, 42167, 193965, 282203, and no false positives up to 22.5k

Originally Posted by T.Rex

It works fine for: 3, 5, 11, 47, 53, 141, 143, 191, 273, 341 . There is a gap till 16541, that should be reached by tomorrow.

It does not work for n=3 and n=5 right?
2^3+5 = 13, S0=194, S1=12.
2^5+5 = 37. S0=194, S1=5, S2=23, S3=9.

[axn]

Originally Posted by ATH

It does not work for n=3 and n=5 right?
2^3+5 = 13, S0=194, S1=12.
2^5+5 = 37. S0=194, S1=5, S2=23, S3=9.

194%13=12
194%37=9

So they work (as long as you take mod).

[ATH]

Originally Posted by axn

194%13=12
194%37=9

So they work (as long as you take mod).

Right, sorry, I'm an idiot. I forgot when N<S0 I have to do S0%N