mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

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

2×457 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2015-08-27, 10:58   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×5×353 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2015-08-27, 12:15   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2015-08-27, 12:45   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2015-08-27, 12:58   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39216 Posts
Default ..., 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
T.Rex is offline   Reply With Quote
Old 2015-08-27, 13:00   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101110010102 Posts
Default

GMP might be quicker -- it depends on programming C

Last fiddled with by paulunderwood on 2015-08-27 at 13:02
paulunderwood is offline   Reply With Quote
Old 2015-08-27, 13:28   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

OK. Wait and see if someone is interested in coding this.
Probably that someone would like to find new big PRPs ! ;)
T.Rex is offline   Reply With Quote
Old 2015-08-27, 13:40   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

DCA16 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2015-08-27, 13:51   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2015-08-27, 13:58   #10
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
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
science_man_88 is offline   Reply With Quote
Old 2015-08-27, 14:00   #11
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22·5·397 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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!

Xyzzy is offline   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 - 2·A261539: (2^n+5)/3 , n even T.Rex Miscellaneous Math 38 2015-09-05 16:14
OEIS - A059242 : 2^n+5 , n odd T.Rex Miscellaneous Math 7 2015-08-28 18:04
my misunderstanding of the OEIS science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 22:14.

Sat Jan 16 22:14:08 UTC 2021 up 44 days, 18:25, 0 users, load averages: 2.26, 2.54, 2.32

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.