Searching for Wagstaff PRP

[T.Rex]

Originally Posted by Cybertronic

short addition :

Seems you have found a cycle and a seed. It gives 14 when q%2=2 and 194 when q%3=1.

You should use gp/PARI !
s=14;q=17;W=(2^q+1)/3;S=s;for(i=1,q-2,S=Mod(S^2-2,W);print(S))

Interesting...

Thanks !

Tony

[Cybertronic]

Thanks!

You have right: p mod 3=2 -> S=14 , p mod 3=1 -> S=194

Curios, for both numbers (2^p+1)/3 and (2^p+1) work this program correct.

It is not an accident, it is an coherence.

[T.Rex]

Originally Posted by Cybertronic

Curios, for both numbers (2^p+1)/3 and (2^p+1) work this program correct. It is not an accident, it is an coherence.

Yes. That can be proved.

Continue to search. If you find a universal (for all Wagstaff primes) seed that leads to a cycle of la ength that divides q-1, I'm very interested !!

Tony

[ixfd64]

Even though this is only a conjecture at the moment, it is still a major milestone in number theory. I'm surprised that no academic sources have picked up on it yet. I e-mailed MathWorld and Chris Caldwell but never got any response. Anyone else want to try?

[Cybertronic]

Like I said, me is it known since over 10 years but it was declined.

I can't proved it, I have to little know how.

It is NOT a trivial fermat test, still it is true for wagstaff primes.

AND !

It is also for prime of form 2^n+3 : Here we have more exponents, because not only a prime.

10 P=2
20 N=2^P+3
30 T=1:S=14
40 S=(S^2 mod N)-2
50 inc T
60 if T=P then goto 100
70 goto 40
100 if or{S=(14 mod N),S=(194 mod N)} then print P;
120 P=P+1:goto 20

run
3 4 6 7 12 15 16 18 28 30 55 67 84 228 390 784 1110 1704 2008 2139 2191 2367 2370
Break in 40

[T.Rex]

Originally Posted by ixfd64

Even though this is only a conjecture at the moment, it is still a major milestone in number theory. I'm surprised that no academic sources have picked up on it yet. I e-mailed MathWorld and Chris Caldwell but never got any response. Anyone else want to try?

I've already tried.
Samuel Wagstaff was interested in Vrba conjecture and he asked a student to work on it, with no success.
HC Williams was also interested in my attempt to prove my conjecture for Mersenne Cycles (a first step before Vrba conjecture) and he gave me some help. I have put on my site a paper summarizing the ideas I've explored (still with the Ribenboim/Williams techniques, based on Lucas series, but with an idea of using the period of a special Lucas sequence. And it may be all nuts...).

I think that there is an interesting study to be done on the properties of the Cycles of a DiGraph for Mersennes, Wagstaff and Fermat numbers. Some kind of continuing the work done by Shallit&Vasiga. By experimentations, I've found interesting properties dealing with Cycles of the DiGraph under x^2-2 modulo a Mersenne prime that some other people have proven. More should be discovered.

What is the most important, I think, is:
1) to prove an efficient primality test for numbers that are not exactly N+1 or N-1 (with N easily factorizable), like Wagstaff numbers are, and
2) to explore the possibility to prove that a number is NOT prime must faster than with LLT or with other methods (except finding a factor !!) by using the property of a Cycle that divides q-2. My hope is that it will help to prove that a Fermat number is NOT prime much faster than searching by chance for a factor or by running Pépin's test (which would require years for last status-unknown candidate).

Moreover, this technique (use Cycles or Trees) can be extended to other kinds of numbers and with other functions than x^2-2. Edouard Lucas found some tests of this kind, but without (as usual for him !) providing a perfect modern proof that is today required. If Lucas had found this new Wagstaff PRP, he would have said: It's a prime ! like he did for other Mersenne primes, at a time he had not provided a full proof, before Lehmer came.

Look at this page for all explainations and useful paper.

Tony

[philmoore]

Your number now is listed on the Lifchitz site:

http://www.primenumbers.net/prptop/prptop.php

The third mega-digit prp - congratulations, and go find another!

[T.Rex]

Originally Posted by philmoore

Your number now is listed on the Lifchitz site:
http://www.primenumbers.net/prptop/prptop.php
The third mega-digit prp - congratulations, and go find another!

Good !
Yes ! With mountains, there is a limit... But, with PRPs or primes, there is no limit ! So, yes, already looking for another one ! One more year or more to wait for a new one ?! :)
Tony

[axn]

At the risk of derailing the thread, the V-R test can be generalized for non-base-2 primes (both for generalized repunits (b^n-1)/(b-1) and generalized wagstaff (b^n+1)/(b+1))

[T.Rex]

Originally Posted by axn

At the risk of derailing the thread, the V-R test can be generalized for non-base-2 primes (both for generalized repunits (b^n-1)/(b-1) and generalized wagstaff (b^n+1)/(b+1))

Good !!! Do you have examples for generalized Wagstaff ?
Tony

[axn]

Originally Posted by T.Rex

Good !!! Do you have examples for generalized Wagstaff ?
Tony

For base 3:
Define f(x) = x^3-3*x
Test for N=(3^p-1)/(3-1): s₀=4, s_i+1=f(s_i), s_ps₁ (mod N)
Test for N=(3^p+1)/(3+1): s₀=8, s_i+1=f(s_i), s_ps₁ (mod N)

For each base, we have to define a different f(x) and find proper seeds.