mersenneforum.org OEIS - A059242 : 2^n+5 , n odd
 Register FAQ Search Today's Posts Mark Forums Read

 2015-08-27, 18:20 #1 T.Rex     Feb 2004 France 39A16 Posts OEIS - A059242 : 2^n+5 , n odd See: https://oeis.org/A059242 . The LLT-like algorithm, base on a cycle, is described by this PARI/gp program: Code: 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 ! Last fiddled with by T.Rex on 2015-08-27 at 18:23
2015-08-27, 18:22   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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: Code: 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 !
Code:
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.

Last fiddled with by science_man_88 on 2015-08-27 at 18:22

2015-08-27, 18:46   #3
T.Rex

Feb 2004
France

2×461 Posts

Quote:
 Originally Posted by science_man_88 Code: a=[];forstep(i=100000,1,-1,n=i<<1+1;N=1<
Hummmm That shows nothing on my old Pari/gp on Windows. Should I update it ?

2015-08-27, 18:52   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 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.

Code:
(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.

Last fiddled with by science_man_88 on 2015-08-27 at 18:59

 2015-08-28, 07:11 #5 T.Rex     Feb 2004 France 2×461 Posts 16541 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.
2015-08-28, 12:25   #6
ATH
Einyen

Dec 2003
Denmark

32·5·71 Posts

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

Quote:
 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.

Last fiddled with by ATH on 2015-08-28 at 12:25

2015-08-28, 13:18   #7
axn

Jun 2003

3·11·157 Posts

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

2015-08-28, 18:04   #8
ATH
Einyen

Dec 2003
Denmark

32×5×71 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post lidocorc Information & Answers 1 2016-12-11 07:26 T.Rex Miscellaneous Math 40 2015-09-15 14:01 T.Rex Miscellaneous Math 38 2015-09-05 16:14 science_man_88 Miscellaneous Math 11 2011-05-18 15:04

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

Wed Dec 1 18:08:34 UTC 2021 up 131 days, 12:37, 3 users, load averages: 2.18, 1.60, 1.42