mersenneforum.org OEIS - A057732 : 2^n + 3
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2015-08-27, 10:47 #1 T.Rex     Feb 2004 France 39A16 Posts OEIS - A057732 : 2^n + 3 Hi, I think that I have a LLT-like method for finding OEIS A057732 PRPs. Now, up to 31th number (8739), I have the same results that OEIS shows. (A057732 numbers are primes and PRPs numbers of the form: 2^n + 3. See: https://oeis.org/A057732) I'd like to know which method has been used for finding the big A057732 numbers, like the top ones: 479844 (prime) and 685578 (PRP). Thx
 2015-08-27, 10:58 #2 paulunderwood     Sep 2002 Database er0rr 393410 Posts I don't think you should have said "479844 (prime)" Here are the known gigantic PRPs, some well within the reach of ECPP in a reasonable amount of time. My guess is that these PRPs were found with NewPGen+PFGW. Last fiddled with by paulunderwood on 2015-08-27 at 11:15
 2015-08-27, 12:15 #3 T.Rex     Feb 2004 France 2·461 Posts Yes. reading again the OEIS A057732 page, it seems clear now that the biggest exponents give PRPs. However, the name of this OEIS is bad: "Numbers n such that 2^n + 3 is prime." I should have had a look at OEISA057733 which shows that biggest n giving a prime for 2^n+3 is 228. Since my method finds all 2^n+3 primes in A057733 plus n = 390, 784, 1110, 1704, 2008, 2139, 2191, 2367, 2370, 4002, 4060, 4062, 4552, 5547, 8739 , with no false positive and no false negative, I think that my method is interesting. NewPGen+PFGW ? OK. I no more know how to use them. Last fiddled with by T.Rex on 2015-08-27 at 12:48
 2015-08-27, 12:45 #4 T.Rex     Feb 2004 France 2·461 Posts LLT-like method based on Cycles My method is based on the LLT (Lucas-Lehmer Test), as usual. It makes use of cycles, since the DiGraph x^2-2 modulo (2^n+3) primes does no generate a tree, but only cycles with small trees attached to the cycles. And it makes uses of 2 possible seeds S0. The general formula is: N=2^n+3 ; s(0)=S0 ; s(i+1)=s(i)^2-2 modulo N. If s(j) == S0 then N is prime. In our case, I've found 2 different seeds S0: 14 and (N-5)/2, but with a different number of steps j for each and depending if n is even or odd. In short, in the PARI/gp language, there are 2 sets of 2 formulae, which both (seem to) give all prime N=2^n+3 : 1) Seed S0 = 14 - n odd: n-1 steps for(i=1,100000,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"))) - n even: n-2 steps for(i=1,100000,n=2*i ;N=2^n+3;x=14;for(j=1,n-2,x=Mod(x^2-2,N));if(x==14,print(n," Prime"))) 2) Seed S0 = (N-5)/2 - n odd: n-1 steps for(i=1,100000,n=2*i+1;N=2^n+3;S=(N-5)/2;x=S;for(j=1,n-1,x=Mod(x^2-2,N));if(x==S,print(n," Prime"))) - n even: n-1 steps for(i=1,100000,n=2*i ;N=2^n+3;S=(N-5)/2;x=S;for(j=1,n-1,x=Mod(x^2-2,N));if(x==S,print(n," Prime"))) Probably that second case is simpler, since the number of steps is the same for both n odd and n even, and thus there is only 1 case. If you copy and paste the formulae into gp, you'll have the PRPs. And, since we have now a new method for finding PRPs for 2^n+3, these PRPs are more close to be prime ! ;) We just lack a proof ! Anyway, if Jean Pené could have a look and see if he can implement this PRP test easily, that would generate interesting BIG PRPs. Last fiddled with by T.Rex on 2015-08-27 at 12:54
 2015-08-27, 12:58 #5 T.Rex     Feb 2004 France 2·461 Posts ..., 17187, 17220, 17934 My testing is still running, and my PARI/gp code has just found: 17187, 17220, and 17934. Still no missing n such that 2^n+3 is PRP and still no false positive. (still done with first set of formulae) Sure that PARI/gp is too slow. Maybe someone can implement the algorithm is some C-coded LLT program. Last fiddled with by T.Rex on 2015-08-27 at 12:59
 2015-08-27, 13:00 #6 paulunderwood     Sep 2002 Database er0rr 2×7×281 Posts GMP might be quicker -- it depends on programming C Last fiddled with by paulunderwood on 2015-08-27 at 13:02
 2015-08-27, 13:28 #7 T.Rex     Feb 2004 France 2·461 Posts OK. Wait and see if someone is interested in coding this. Probably that someone would like to find new big PRPs ! ;)
 2015-08-27, 13:40 #8 paulunderwood     Sep 2002 Database er0rr 2·7·281 Posts As for finding new big PRPs, NewPGen+PFGW/LLR is the way to go as it will use George's libraries. Your LLT offers little speed gain over a base 3 Fermat PRP test. When I get a spare hour I will hack some GMP to get your LLT running
 2015-08-27, 13:51 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts It takes ~7 minutes on my computer to get to 17934 using GMP and the simple method of running an ES BPSW test on each value. Code: perl -Mntheory=:all -MMath::GMPz -E 'for (1..1e9) { say if is_prob_prime(Math::GMPz->new(2)**\$_+3) }' Pari/GP simple method, using a relatively similar test (slightly less stringent), takes 20 minutes. Code: for(n=1,1e9,if(ispseudoprime(2^n+3),print1(n", "))) It'd be interesting to compare the new test. Also note that after 3k or so digits, gwnum starts being faster than GMP, and at 50k+ digits it is a lot faster. So OpenPFGW will probably be faster at the very large sizes regardless.
2015-08-27, 13:58   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by T.Rex Sure that PARI/gp is too slow. Maybe someone can implement the algorithm is some C-coded LLT program.
that may be true but there's a lot of possible small improvements in theory that I've been told about over the years instead of 2*i replace it with i<<1, instead of 2^n replace with 1<<n, instead of x^2 use sqr(x) or maybe even use the sqr function outside the Mod and subtract two after that ( or Mod your original value and then do the math in a way that carries it through without having to use Mod again. instead of using things like 1,n-1 use 2,n and since it's iterative other than a number you want to print you can do things in reverse with a step of -1 in a forstep. edit: the outer loop can potentially broken down with PARI/gp's new parallel parfor and grouping by number of threads in theory ( though I suck at that part). edit2: of course you can also delay printing by concatenating into a vector and printing ( or returning) only once.

Last fiddled with by science_man_88 on 2015-08-27 at 14:53

2015-08-27, 14:00   #11
Xyzzy

Aug 2002

22×2,089 Posts

Quote:
 Originally Posted by T.Rex Hi, I think that I have a LLT-like method for finding OEIS A057732 PRPs.
It sure has been a long time since you visited! We were worried about you!

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

All times are UTC. The time now is 13:34.

Fri Dec 3 13:34:26 UTC 2021 up 133 days, 8:03, 0 users, load averages: 1.43, 1.23, 1.19