OEIS - A057732 : 2^n + 3

[T.Rex]

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

[paulunderwood]

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.

[T.Rex]

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.

[T.Rex]

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.

[T.Rex]

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.

[paulunderwood]

GMP might be quicker -- it depends on programming C

[T.Rex]

OK. Wait and see if someone is interested in coding this.
Probably that someone would like to find new big PRPs ! ;)

[paulunderwood]

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

[danaj]

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.

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.

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.

[science_man_88]

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.

[Xyzzy]

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!