Universal seeds of the LLT for Mersenne and Wagstaff numbers

[T.Rex]

You probably know that there are 3 Universal Seeds for starting the LLT for Mersenne numbers: 4, 10, and 2/3.
It appears that 2/3 modulo Mq = (2^q+1)/3 = Wq, a Wagstaff number.

Also, you may know that there is a conjecture about proving that a Wagstaff number Wq is prime by using a cycle of the DiGraph under x^2-2 modulo Wq. The seed we found years ago is : 1/4. And kijinSeija found that 1/4 = W(q-2).

Moreover, I've found that 1/10 and 1/Mq seem also to be usable as Universal Seed for this conjecture, building a new bridge between Mersenne and Wagstaff primes, since the seeds of the Wagstaff conjecture are inverse modulo Wq of the Universal Seeds of the Mersenne LLT.

Pari/gp:
T(q)={M=2^q-1;W=(2^q+1)/3;S0=Mod(1/4,W);S=S0;print(S);for(i=1,q+1,S=Mod(S^2-2,W);print(S))}

Try and replace 1/4 by 1/10 and 1/Mq.
It's perfectly clear for 1/4 and 1/10.
It's a little bit different for 1/Mq. It seems to depend if q=4k+1 or 4k-1. It needs deeper study.

[paulunderwood]

Originally Posted by T.Rex

You probably know that there are 3 Universal Seeds for starting the LLT for Mersenne numbers: 4, 10, and 2/3.
It appears that 2/3 modulo Mq = (2^q+1)/3 = Wq, a Wagstaff number.

Also, you may know that there is a conjecture about proving that a Wagstaff number Wq is prime by using a cycle of the DiGraph under x^2-2 modulo Wq. The seed we found years ago is : 1/4. And kijinSeija found that 1/4 = W(q-2).

Moreover, I've found that 1/10 and 1/Mq seem also to be usable as Universal Seed for this conjecture, building a new bridge between Mersenne and Wagstaff primes, since the seeds of the Wagstaff conjecture are inverse modulo Wq of the Universal Seeds of the Mersenne LLT.

Pari/gp:
T(q)={M=2^q-1;W=(2^q+1)/3;S0=Mod(1/4,W);S=S0;print(S);for(i=1,q+1,S=Mod(S^2-2,W);print(S))}

Try and replace 1/4 by 1/10 and 1/Mq.
It's perfectly clear for 1/4 and 1/10.
It's a little bit different for 1/Mq. It seems to depend if q=4k+1 or 4k-1. It needs deeper study.

I just found this works for (2/3)^-1

wag(q)=W=(2^q+1)/3;S0=S=Mod(3/2,W);for(i=2,q,S=S^2-2);S==S0;

So maybe there is some relationship between inverse seeds for Mersenne and Wagstaff. I.e if S0 is a Mersenne seed then 1/S0 is a Wagstaff seed.

Are 4, 10 and 2/3 the only ones for Mersenne? I remember Lehmer had said something about these.

[paulunderwood]

More on the seed 3/2 for Wagstaff numbers.

Mod(Mod(x,W),x^2-3/2*x+1) is at the heart because S = S0 = 3/2 = x+1/x which leads to the recurrence S=S^2-2 mod W

The solution for x is ( 3/2 +- sqrt( (3/2)^2-4 ) / 2 = ( 3 +- 2 * sqrt(2) ) / 4

That is 4*x - 3 == +- 2 * sqrt(2)

So we can use a power of Mod(Mod(4*x-3,W),x^2-8).

By trial and error Mod(Mod(4*x-3,W),x^2-8)^(W+1)+119 == 0

Edit. That marked red is wrong, but somehow the result is good!

Stumped!

[kriesel]

Originally Posted by paulunderwood

Are 4, 10 and 2/3 the only ones for Mersenne? I remember Lehmer had said something about these.

https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.

The ninth page of Bas Jensen's PhD number theory thesis https://scholarlypublications.univer...3A2919366/view makes reference to a 1996 conjecture by G. Woltman, proven 4 years later.

[ATH]

Originally Posted by kriesel

https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.

The ninth page of Bas Jensen's PhD number theory thesis https://scholarlypublications.univer...3A2919366/view makes reference to a 1996 conjecture by G. Woltman, proven 4 years later.

There are at least 2 infinite series of universal starting values starting from the known 4 and 10
https://www.mersenneforum.org/showpo...0&postcount=46

A₀=A₁=4, A_N=14*A_N-1-A_N-2
B₀=B₁=10, B_N=98*B_N-1-B_N-2

[T.Rex]

Originally Posted by kriesel

https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.

Not exactly. There are 2^x (cannot remember the exact value, x depends on q, and I'm now typing on my phone) seeds for each Mq. But there are only 3 F IXED values which can be used for all Mq.

I see that 2/3 = Wq was already known.

[T.Rex]

Originally Posted by paulunderwood

I just found this works for (2/3)^-1

Good !
Thanks !
I should have checked Yesterday.

[paulunderwood]

Originally Posted by T.Rex

Good !
Thanks !
I should have checked Yesterday.

It is not so great since (3/2)^2-2 = 1/4 which is already known.

Just as (3)^((Mp - 1)/2) == -1 mod Mp for Mersenne primes, we have (-7)^((Wq - 1)/2) == 1 mod Wq for Wagstaff PRPs. The latter can be 7^((Wq - 1 )/2) == -1 mod Wq.

[kriesel]

Originally Posted by T.Rex

Not exactly.

I thought later after I posted that, that seed > Mp or Mp² would be some sort of problem. But it seems to work, at least in a very small sample tried.
The wikipedia article should be updated if it's wrong.

[T.Rex]

Hello.
I've spent some time searching for Universal Seeds for the LLT-like test for Wagstaff numbers.
Here attached is a first set of findings.
Everything has been checked for all known Wagstaff primes and for Wagstaff not-primes up to q = 10,000.
It may be strange, but 23/8 mod Wq is a Universal seed!
And 1/10 is, sometimes...
Enjoy
Tony

[ixfd64]

Probably a stupid question, but my knowledge is not up to scratch.

It is my understanding that "2/3" is shorthand for (2 mod M(p))(3 mod M(p))^-1 = W(p). I was indeed able to confirm that W(p) works as a seed value when testing whether M(p) is prime. However, it's not clear how (2 mod M(p))(3 mod M(p))^-1 evaluates to a Wagstaff number.

I can see where the "2/3" comes from because 2 mod M(p) = 2 and 3 mod M(p) = 3 for p > 2. But it doesn't make sense to use a fraction as a seed value. Or does (3 mod M(p))^-1 mean something other than 1 / (3 mod M(p)) in this case?