20150827, 10:47  #1 
Feb 2004
France
1637_{8} Posts 
OEIS  A057732 : 2^n + 3
Hi,
I think that I have a LLTlike 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 
20150827, 10:58  #2 
Sep 2002
Database er0rr
5·829 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 20150827 at 11:15 
20150827, 12:15  #3 
Feb 2004
France
3^{2}×103 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 20150827 at 12:48 
20150827, 12:45  #4 
Feb 2004
France
1110011111_{2} Posts 
LLTlike method based on Cycles
My method is based on the LLT (LucasLehmer Test), as usual.
It makes use of cycles, since the DiGraph x^22 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)^22 modulo N. If s(j) == S0 then N is prime. In our case, I've found 2 different seeds S0: 14 and (N5)/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: n1 steps for(i=1,100000,n=2*i+1;N=2^n+3;x=14;for(j=1,n1,x=Mod(x^22,N));if(x==14,print(n," Prime")))  n even: n2 steps for(i=1,100000,n=2*i ;N=2^n+3;x=14;for(j=1,n2,x=Mod(x^22,N));if(x==14,print(n," Prime"))) 2) Seed S0 = (N5)/2  n odd: n1 steps for(i=1,100000,n=2*i+1;N=2^n+3;S=(N5)/2;x=S;for(j=1,n1,x=Mod(x^22,N));if(x==S,print(n," Prime")))  n even: n1 steps for(i=1,100000,n=2*i ;N=2^n+3;S=(N5)/2;x=S;for(j=1,n1,x=Mod(x^22,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 20150827 at 12:54 
20150827, 12:58  #5 
Feb 2004
France
927_{10} 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 Ccoded LLT program. Last fiddled with by T.Rex on 20150827 at 12:59 
20150827, 13:00  #6 
Sep 2002
Database er0rr
1000000110001_{2} Posts 
GMP might be quicker  it depends on programming C
Last fiddled with by paulunderwood on 20150827 at 13:02 
20150827, 13:28  #7 
Feb 2004
France
3^{2}×103 Posts 
OK. Wait and see if someone is interested in coding this.
Probably that someone would like to find new big PRPs ! ;) 
20150827, 13:40  #8 
Sep 2002
Database er0rr
4145_{10} 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 
20150827, 13:51  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1615_{8} 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) }' Code:
for(n=1,1e9,if(ispseudoprime(2^n+3),print1(n", "))) 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. 
20150827, 13:58  #10 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
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,n1 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 20150827 at 14:53 
20150827, 14:00  #11 
Aug 2002
2·4,229 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Adding M(37156667) to OEIS  lidocorc  Information & Answers  1  20161211 07:26 
OEIS  2·A261539: (2^n+5)/3 , n even  T.Rex  Miscellaneous Math  38  20150905 16:14 
OEIS  A059242 : 2^n+5 , n odd  T.Rex  Miscellaneous Math  7  20150828 18:04 
my misunderstanding of the OEIS  science_man_88  Miscellaneous Math  11  20110518 15:04 