OEIS - (2^n-5)/3 - n odd - LLT-like algorithm for finding PRPs

[T.Rex]

It looks like this sequence (n such that (2^n-5)/3 is prime or PRP, n odd) does not exist in OEIS:

7, 13, 19, 31, 51, 55, 85, 111, 319, 373, 505, 811, 901, 943, 1117, 2199, 2431,

There are 2 cases, depending if n == 0 mod 3 or not.

1) n == 1 or 2 mod 3

for(i=3, 10000, n=2*i+1; N=(2^n-5)/3; s=4; s=s^2-2; x=s; for(j=1, n-1, x=Mod(x^2-2,N)); if(x==s, print1(n,", ")))
7, 13, 19, 31, 55, 85, 319, 373, 505, 811, 901, 943, 1117, 2431, 5059,

2) n == 0 mod 3

for(i=3, 10000, n=2*i+1; if(Mod(n,3)==0, N=(2^n-5)/3; s=13; s=s^2-2; x=s; for(j=1, n-1, x=Mod(x^2-2,N)); if(x==s, print1(n,", "))))
51, 111, 2199,

My Pari/gp programs are still running for completing the 3 sequences up to 10000. I will update the post then.

[science_man_88]

Originally Posted by T.Rex

It looks like this sequence (n such that (2^n-5)/3 is prime or PRP, n odd) does not exist in OEIS:

7, 13, 19, 31, 51, 55, 85, 111, 319, 373, 505, 811, 901, 943, 1117, 2199, 2431,

There are 2 cases, depending if n == 0 mod 3 or not.

1) n == 1 or 2 mod 3

for(i=3, 10000, n=2*i+1; N=(2^n-5)/3; s=4; s=s^2-2; x=s; for(j=1, n-1, x=Mod(x^2-2,N)); if(x==s, print1(n,", ")))
7, 13, 19, 31, 55, 85, 319, 373, 505, 811, 901, 943, 1117, 2431, 5059,

2) n == 0 mod 3

for(i=3, 10000, n=2*i+1; if(Mod(n,3)==0, N=(2^n-5)/3; s=13; s=s^2-2; x=s; for(j=1, n-1, x=Mod(x^2-2,N)); if(x==s, print1(n,", "))))
51, 111, 2199,

My Pari/gp programs are still running for completing the 3 sequences up to 10000. I will update the post then.

not sure why you are making a new pari/gp program each time:

http://mersenneforum.org/showpost.ph...&postcount=396

is my combo of TF and LLT into one for the mersennes just append the values needed and it can work for any of these for TF or LL.

[T.Rex]

Originally Posted by science_man_88

not sure why you are making a new pari/gp program each time:

http://mersenneforum.org/showpost.ph...&postcount=396

is my combo of TF and LLT into one for the mersennes just append the values needed and it can work for any of these for TF or LL.

I'm just copying as-is the exact code that proved to provide correct results.
I do not understand your code. Which language ? I know basic PARI/gp code only.

The difficulty is to find a universal initial value (the seed) and a number of iterations that work fine with all primes (or PRPs) of the sequence being studied, and to deal with exceptions (n== 0 mod 3 like here). However, it is not so difficult. But I never thought to start from a seed which is outside of the cycle.

[science_man_88]

Originally Posted by T.Rex

I'm just copying as-is the exact code that proved to provide correct results.
I do not understand your code. Which language ? I know basic PARI/gp code only.

The difficulty is to find a universal initial value (the seed) and a number of iterations that work fine with all primes (or PRPs) of the sequence being studied, and to deal with exceptions (n== 0 mod 3 like here). However, it is not so difficult. But I never thought to start from a seed which is outside of the cycle.

it is all basic pari/gp basically here's the explanation basically in the gimps math section it says that during TF to test a factor we write the exponent in binary and then it checks to see if the value in the binary is 1 and does a computation if it is and another if it's not in the case of LL since it does the same calculation regardless we can see it as all 1's or all 0's and so it only really has one branch in the conditional it then checks the result in the case of TF against 1 ( because ) and in the LL part against 0 because in the normal LL for mersennes we want to know if the final result is 0. all we need to do is alter the inputs for the given flag value to match a certain type of number.

[T.Rex]

isprime() returns:

7, 13, 19, 31, 51, 55, 85, 111, 319, 373, 505, 811, 901, 943, 1117, 2199, 2431, 5059,

[T.Rex]

There is an issue with n==0 mod 3. Maybe 21 should be used as seed instead of 13, which misses 2199.
More values are required.

[paulunderwood]

Tony, this brings into question how you choose the seeds.

[danaj]

For comparison, I get these BPSW PRPs from my program:

7, 13, 19, 31, 51, 55, 85, 111, 319, 373, 505, 811, 901, 943, 1117, 2199, 2431, 5059, 9423, 12601, 20295, 22755, 38659, 57219, 64179, ...

[paulunderwood]

Originally Posted by paulunderwood

Tony, this brings into question how you choose the seeds.

And the validity of the Reix-Vbra tests we ran for Wagstaff (up to exponent 10,000,000.)

[primus]

My solution :

For n>10 and n is odd .

PPT(n)=
{ 
my(s=Mod(6,(2^n-5)/3));
for(i=1,n-1,s=s^2-2);
s==2*polchebyshev(4,1,3)
}

[Batalov]

Originally Posted by paulunderwood

And the validity of this???

How is one "solution" different from another? One unproven hunch over another unproven hunch?
With both slower than a Fermat PRP test (which is proven to find all primes and PRPs), too!