mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

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

2·457 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2015-08-27, 18:22   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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
science_man_88 is offline   Reply With Quote
Old 2015-08-27, 18:46   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
Hummmm That shows nothing on my old Pari/gp on Windows. Should I update it ?
T.Rex is offline   Reply With Quote
Old 2015-08-27, 18:52   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

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

11100100102 Posts
Default 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.
T.Rex is offline   Reply With Quote
Old 2015-08-28, 12:25   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·17·59 Posts
Default

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 View Post
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
ATH is online now   Reply With Quote
Old 2015-08-28, 13:18   #7
axn
 
axn's Avatar
 
Jun 2003

10010111010102 Posts
Default

Quote:
Originally Posted by ATH View Post
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).
axn is online now   Reply With Quote
Old 2015-08-28, 18:04   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

57018 Posts
Default

Quote:
Originally Posted by axn View Post
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
ATH is online now   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 - 2·A261539: (2^n+5)/3 , n even T.Rex Miscellaneous Math 38 2015-09-05 16:14
my misunderstanding of the OEIS science_man_88 Miscellaneous Math 11 2011-05-18 15:04

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

Thu Jan 21 08:53:07 UTC 2021 up 49 days, 5:04, 0 users, load averages: 3.17, 3.48, 3.22

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