DiGraph under x^2-2 modulo a Wagstaff number

T.Rex · 2023-01-10, 18:11

I have written a C program which computes the cycles of the DiGraph under x^2-2 modulo the Wagstaff numbers with q prime from 7 to 31 (Only W29 is not prime).

The results are:

Code:

q:   7 ----------------------------

length  number
     1       2  |          2 -> ...
     3       1  |          8 -> ...
     5       1  |          4 -> ...
     6       1  |         23 -> ...

q:  11 ----------------------------

length  number
     1       2  |          2 -> ...
     3       1  |        211 -> ...
     5       4  |        223 -> ...
     9       9  |         47 -> ...
    10      15  |         14 -> ...

q:  13 ----------------------------

length  number
     1       2  |          2 -> ...
     2       1  |        755 -> ...
     3       1  |       1758 -> ...
     4       1  |       1074 -> ...
     6       6  |         18 -> ...
    11      31  |          4 -> ...
    12      53  |          3 -> ...

q:  17 ----------------------------

length  number
     1       2  |          2 -> ...
     2       1  |       4906 -> ...
     4       2  |      21843 -> ...
     5       3  |      37607 -> ...
     8      20  |        127 -> ...
    15     363  |        527 -> ...
    16     672  |          3 -> ...

q:  19 ----------------------------

length  number
     1       2  |          2 -> ...
     3       2  |     138706 -> ...
     6       4  |       4861 -> ...
     9      37  |        171 -> ...
    17    1285  |         47 -> ...
    18    2407  |         23 -> ...

q:  23 ----------------------------

length  number
     1       2  |          2 -> ...
     7       9  |    2529946 -> ...
    11     124  |    1292767 -> ...
    21   16641  |         47 -> ...
    22   31713  |         14 -> ...

q:  29 ----------------------------

length  number
     1       4  |          2 -> ...
     2       6  |   24924406 -> ...
     3       2  |   63039968 -> ...
     4       4  |  139525776 -> ...
     6       1  |   76119878 -> ...
    12       9  |   56973630 -> ...
    14      22  |   89478483 -> ...
    28      24  |  154455222 -> ...
    42       1  |     290653 -> ...
    84       2  |   70628741 -> ...
   363      18  |   12228457 -> ...
   726       9  |  105518052 -> ...
  1452       9  |   20984038 -> ...
  5082       9  |   69754008 -> ...
 10164     198  |         47 -> ...
 21665       2  |    5299202 -> ...
 43330       8  |      91807 -> ...
 86660      23  |       1022 -> ...
129990      18  |        254 -> ...
259980      46  |         23 -> ...

q:  31 ----------------------------

length  number
     1        2 |         2 -> ...
     3        1 | 288941458 -> ...
     5        6 |     32768 -> ...
     6        1 |  79007128 -> ...
    10       48 |     12425 -> ...
    15     1454 | 141681407 -> ...
    29  3085465 |        47 -> ...
    30  5964488 |        23 -> ...

where "length" is the length of cycles and "number" the number of cycles of such a length.
When Wq is prime, the length always divides either q-1 or q-2.

Where "X -> ..." is an example of such a cycle, giving the first element of the cycle.

It appears that the number of cycles for length equal to q-2 and q-1 is given by the OEIS list
A165921 :

Code:

n		a(n)
...
5		1
6		1
...
9		9
10		15
11		31
12		53
...
15		363
16		672
17		1285
18		2407
...
21		16641
22		31713
...
29		3085465
30		5964488

Moreover, some new S0 seeds appear, for cycles of length q-2 or q-1, depending if q = +1 or -1 mod(4) or mod6).

Code:

-1 mod 4 : q=7, 11, 19, 23, 31
                3 -> 7 -> 47 -- q-2 -> 47 
+1 mod 4 : q=13, 17, 29
                3 -- q-1 -> 3

-1 mod 6 : q=11, 17, 23, 29
                4 -> 14 -- q-1 -> 14
                5 -> 23 -> 527 -- q-2 -> 527
+1 mod 6 : q=13, 19, 31
                4 -- q-2 -> 4
                5 -> 23 -- q-1 -> 23

There are some other cases, starting from 5, 8, or 9. Less interesting.

More interesting are the three following universal seeds (in addition to 3/2 (or 1/4) used by Gerbicz):

Code:

S0=1154:
6 -> 34 -> 1154 -- q-3 -> -34 -> 1154

which is the seed used by Vrba in his paper.

Code:

S0=23/8 mod Wq
S0=Mersenne(q-3)=2^(q-3)-1

And, much more interesting ! :

Code:

S0=5^2+1/5^2

which is the parallel for Wagstaff numbers to the seed 3^2+1/3^2 I was using for Mersenne numbers in my conjecture.
(Using S0=k^2+1/k^2 fits with several papers I've read.)
I've checked it up to q=3539.
Moreover, we have:

Code:

for n=1 ... q-1 :  5^(2^n) + 1/5^(2^n) = S(n-1) modulo Wq

About q=29, please note that there are 24 cycles of length 28, and none of length 27.
None of these cycles of length 28 run into the known universal seeds 1154, 3/2, 23/8, M(q-3), or 5^2+1/5^2 mod Wq.

Here is some code for checking validity of the seeds:

Code:

Cycle of length q-2:
forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(1154,w);        s=s0;for(i=1,q-2,s=Mod(s^2-2,w));if(s==s0,print(q)))
Cycles of length q-1:
forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(23/8,w);        s=s0;for(i=1,q-1,s=Mod(s^2-2,w));if(s==s0,print(q)))
forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(5^2+1/5^2,w);   s=s0;for(i=1,q-1,s=Mod(s^2-2,w));if(s==s0,print(q)))
forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(2^(q-3)-1,w);   s=s0;for(i=1,q-1,s=Mod(s^2-2,w));if(s==s0,print(q)))
forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(3/2,w);         s=s0;for(i=1,q-1,s=Mod(s^2-2,w));if(s==s0,print(q)))

Conclusions :
- When a Wagstaff number is a prime, its DiGraph shows perfect symetries and properties.
- When a Wagstaff number is not a prime, its DiGraph shows some mess.
Thus, how can we use such information for building the "sufficiency" part of the proof of our conjectures ?
How can we prove that, if Wq is not a prime, then the property (use one of the cycles starting with a universal seed) does not stand ?
Which theory/tools can we use ?

T.Rex · 2023-01-10, 21:12

I forgot to talk about the universal seed for q-1 cycle found by kijinSeija: W(q-2).
However, as paulunderwood has shown, it's the same as 1/4 mod Wq.
And (3/2)^2-2 mod Wq = 1/4 Mod Wq.

Note that kijinSeija also found that q^2 is a universal seed for Wagstaff under x2.

Code:

forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(q^2,w);s=s0;for(i=1,q-1,s=Mod(s^2,w));if(s==s0,print(q)))

henryzz · 2023-01-16, 09:40

How do the cycle lengths behave for other composite exponents?
I wonder whether the proportion of very short cycle lengths could be different for composite exponents compared with prime exponents. If so, it may be possible to screen candidates based on checking a few random seeds for length.
To check this, it shouldn't be necessary to calculate all the seeds for larger exponents. A random 1M would be enough(and make comparison easier without calculating %s)

Would be happy to fiddle with your c code if you make it available.

Is there any logic behind the missing cycle lengths? Looking at it, there seem to be patterns, but they often don't quite hold. Maybe this would be clearer for larger exponents?

T.Rex · 2023-02-22, 17:14

Another possible way to find Wagstaff ( $(2^q+1)/3$ PRPs, using a Cycle of length $q-2$ of the DiGraph under $x^2-2$ .

Let: $S_n = S_{n-1}^2 -2 \ mod \ W_q$ .
We have: $6 \ -> \ 34 \ -> \ 1154$ .

It seems that: $W_q$ is (probably) prime iff $S_0=1154 \text{ and } S_{q-2}=S_0$ .

Which is equivallent to say: $W_q$ is (probably) prime iff $S_0=6 \text{ and } S_{q}=1154$ .

The following PARI/gp code checks the above test for all q primes from 11 to 127031.
If the test is sucessful and q belongs to the list of known primes p such that $W_p$ is prime, then: "q +" is printed.
If the test is sucessful and $W_q$ is NOT prime, then "q --" is printed.

Code:

L = [5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031]
f(S0)={forprime(q=11,127031,
                         W=(2^q+1)/3;
                         S=S0;
                         found=0;
                         for(i=1,q-2,
                              S=Mod(S^2-2,W));
                         if(lift(S)==S0,
                             for(j=1,length(L),
                                  if(q==L[j],found=1;break));
                             if(found==1,print(q," +"),print(q," --"))))}
f(1154)
13 +
17 +
19 +
23 +
31 +
43 +
61 +
....

All known Wagstaff primes with $p>11$ are found, and none composite Wagstaff.

T.Rex · 2023-02-28, 11:14

A French mathematician and I are working on this subject.
He has built a formula for computing the length of the cycles. He will very probably publish his work in the next future.
Here are the results I've computed for p prime < 200.

Wagstaff primes:

Code:

 p= 13: [1, 2, 3, 4, 6, 11, 12]
 p= 17: [1, 2, 4, 5, 8, 15, 16]
 p= 19: [1, 3, 6, 9, 17, 18]
 p= 23: [1, 7, 11, 21, 22]
 p= 31: [1, 3, 5, 6, 10, 15, 29, 30]
 p= 43: [1, 3, 6, 7, 14, 21, 41, 42]
 p= 61: [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 59, 60]
 p= 79: [1, 3, 6, 7, 11, 13, 26, 39, 77, 78]
 p=101: [1, 2, 5, 9, 10, 11, 20, 25, 33, 50, 99, 100]
 p=127: [1, 3, 5, 6, 7, 9, 14, 18, 21, 25, 42, 63, 125, 126]
 p=167: [1, 5, 11, 15, 33, 55, 83, 165, 166]
 p=191: [1, 5, 7, 9, 10, 19, 21, 27, 38, 63, 95, 189, 190]
 p=199: [1, 3, 6, 9, 11, 18, 22, 33, 66, 99, 197, 198]

Wagstaff non-primes (when there are too many different lengths, only the 30 first ones are given or at least 2 after p-1. Plus the total number of different lengths):

Code:

p= 29: [1, 2, 3, 4, 6, 12, 14, 28, 42, 84, 363, 726, 1452, 5082, 10164, 21665, 43330, 86660, 129990, 259980]           ... n= 20
p= 37: [1, 3, 7, 18, 21, 36, 126, 252, 8221, 24663, 57547, 58065, 147978, 172641, 295956, 348390, 696780]              ... n= 17
p= 41: [1, 3, 6, 10, 11, 20, 30, 33, 60, 66, 110, 190, 570, 4180, 12540, 42047, 83102, 126141, 166204, 249306, 252282, 415510, 420470, 498612, 831020, 840940, 925034, 1246530, 2493060, 2522820, ... n= 34
p= 47: [1, 2, 3, 6, 23, 35, 39, 46, 69, 70, 78, 83, 92, 105, 138, 210, 498, 805, 897, 1365, 1443, 1794, 1909, 2545, 2730, 2905, 3220, 3818, 5772, 6474, ... n= 85
p= 53: [1, 5, 10, 20, 26, 52, 130, 260, 33627438, 67254876, 168137190, 336274380, 637722971873, 1275445943746, 3188614859365, 6377229718730]               ... n= 16
p= 59: [1, 2, 3, 4, 6, 8, 12, 18, 24, 29, 36, 39, 58, 72, 78, 87, 116, 156, 174, 232, 234, 312, 348, 468, 522, 696, 936, 1044, 1131, 2088, ... n= 128
p= 67: [1, 2, 3, 5, 6, 10, 15, 30, 33, 66, 130, 165, 330, 390, 2559, 4195, 4290, 5118, 8390, 10236, 12585, 12795, 16780, 25170, 25590, 28149, 35229, 50340, 51180, 56298, ... n= 79
p= 71: [1, 2, 3, 6, 35, 70, 105, 140, 210, 1839, 3678, 8754, 17508, 64365, 128730, 257460, 306390, 612780, 2371671, 4743342, 5366202, 7051205, 10732404, 14102410, 21153615, 28204820, 42307230, 76763854, 83008485, 166016970, ... n= 51
p= 73: [1, 9, 18, 135, 270, 438, 1314, 1547, 13923, 19710, 27846, 208845, 417690, 677586, 2032758, 30491370, 51060630, 102121260, 153181890, 306363780, 919091340, 3727425990, 7454851980, 22364555940, 67093667820, 157981589220, 473944767660, 1421834302980, 11532656013060, 34597968039180, ... n= 34
p= 83: [1, 2, 3, 6, 12, 24, 41, 48, 82, 123, 164, 221, 246, 442, 492, 663, 984, 1326, 1968, 2652, 5304, 9061, 9711, 10608, 13973, 18122, 19422, 20061, 27183, 27946, ... n= 216
p= 89: [1, 2, 3, 4, 6, 8, 11, 12, 22, 24, 30, 33, 44, 60, 66, 88, 98, 120, 132, 179, 189, 196, 264, 294, 330, 358, 378, 392, 537, 588, ... n= 522
p= 97: [1, 2, 3, 4, 6, 8, 10, 12, 18, 20, 24, 30, 36, 40, 48, 60, 72, 77, 90, 120, 144, 154, 180, 231, 240, 308, 360, 462, 616, 720, ... n= 131
p=103: [1, 2, 5, 6, 20, 35, 51, 60, 70, 102, 140, 204, 210, 255, 420, 622, 682, 1020, 1244, 1364, 1785, 3570, 7140, 21770, 23870, 31722, 34782, 43540, 47740, 63444, ... n= 135
p=107: [1, 2, 3, 4, 6, 8, 11, 12, 22, 24, 33, 44, 53, 66, 88, 106, 132, 159, 212, 264, 318, 424, 583, 636, 1103, 1119, 1272, 1749, 2206, 2238, ... n= 138
p=109: [1, 2, 3, 4, 6, 8, 12, 14, 18, 24, 26, 28, 36, 42, 48, 52, 72, 78, 84, 104, 126, 144, 156, 168, 182, 234, 252, 312, 336, 364, ... n= 312
p=113: [1, 2, 3, 4, 5, 6, 9, 10, 12, 14, 15, 18, 20, 28, 30, 36, 39, 42, 45, 60, 70, 78, 84, 90, 117, 126, 140, 156, 158, 180, ... n= 978
p=131: [1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20, 21, 28, 30, 37, 42, 60, 65, 74, 84, 111, 130, 148, 195, 202, 222, 251, 260, 370, ... n= 438
p=137: [1, 2, 4, 5, 8, 9, 10, 18, 20, 30, 34, 35, 36, 40, 45, 60, 68, 70, 72, 90, 120, 136, 140, 170, 180, 210, 221, 280, 306, 340, ... n= 1142
p=139: [1, 2, 3, 4, 5, 6, 7, 12, 15, 20, 21, 26, 28, 30, 35, 42, 48, 52, 60, 69, 70, 78, 84, 96, 105, 138, 140, 210, 240, 276, ... n= 775
p=149: [1, 3, 5, 6, 7, 8, 9, 10, 12, 15, 16, 18, 21, 24, 29, 30, 35, 36, 40, 42, 45, 48, 51, 60, 63, 70, 74, 79, 80, 83, 84, 87, 90, 99, 102, 105, 120, 126, 145, 148, 153, 166 ... n= 2444
p=151: [1, 2, 5, 9, 10, 11, 15, 18, 22, 23, 30, 45, 46, 47, 55, 65, 90, 94, 110, 115, 130, 165, 195, 198, 207, 230, 235, 253, 330, 345, ... n= 439
p=157: [1, 2, 3, 4, 6, 11, 12, 14, 22, 26, 28, 30, 33, 42, 44, 52, 60, 66, 78, 83, 84, 88, 104, 105, 132, 142, 154, 156, 166, 182, ... n= 3220
p=163: [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 23, 24, 30, 40, 46, 60, 69, 81, 92, 120, 138, 143, 162, 184, 209, 230, 276, 286, 324, ... n= 1575
p=173: [1, 2, 3, 4, 5, 6, 10, 11, 12, 14, 15, 20, 22, 28, 30, 33, 42, 44, 55, 60, 66, 70, 84, 86, 110, 132, 140, 154, 165, 172, , 210, 220, 233, ... n= 4312
p=179: [1, 2, 4, 9, 14, 18, 22, 28, 30, 36, 44, 60, 89, 90, 126, 154, 178, 179, 180, 210, 252, 308, 323, 330, 356, 386, 420, 630, 660, 772, ... n= 378
p=181: [1, 2, 3, 6, 15, 30, 90, 180, 4861, 9722, 11543, 23086, 34629, 69258, 72915, 145830, 173145, 206493, 346290, 412986, 437490, 874980, 1032465, 1038870, 2064930, 6194790, 12389580, 13883549, 23834330, 27767098, ... n= 331
p=193: [1, 2, 3, 4, 5, 6, 10, 11, 12, 15, 20, 22, 30, 33, 44, 48, 55, 60, 65, 66, 96, 110, 130, 132, 165, 195, 220, 240, 260, 273, ... n= 5354
p=197: [1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 20, 21, 24, 28, 29, 30, 35, 36, 45, 60, 63, 72, 83, 84, 87, 90, 98, 105, 116, 120, 140, 145, 166, 168, 180, 196, 210, 249, ... n= 6565

For not-primes $W_p$ , it is noticeable that there are not always length $p-1$ (for 41, 73, ...), that length $p-2$ never appears, and once there is length $p$ (for 179).

T.Rex · 2023-03-02, 10:01

Here are additionnal results for Wp non-primes.
It is noticeable that p-2 appears as a length of cycles for p=331 (but no p-1 cycle).

So, the conclusion seems to be:
p-1 appears often but not always,
p-2 appears rarely,
both p-1 and p-2 often do not appear.
thus: no clear rule for non-primes Wp !

Code:

p=211: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 18, 20, 21, 22, 23, 25, 28, 30, 33, 35, 36, 42, 44, 45, 46, 50, 55, 60, 63, 66, 69, 70, 75, 77, 84, 90, 92, 99, 100, 105, 110, 115, 126, 132, 138, 140, 142, 150, 154, 161, 165, 175, 180, 186, 190, 198, 210, 220, 225, 230, 231, 252,  ...]
p=223: [1, 2, 24, 29, 37, 48, 58, 74, 98, 146, 148, 196, 888, 1073, 1752, 1776, 2146,  ...]
p=227: [1, 2, 4, 38, 65, 76, 113, 130, 226, 260, 299, 452, 491, 598,  ...]
p=229: [1, 5, 10, 18, 36, 38, 180, 190, 342, 380, 684, 3420, 20474,  ...]
p=233: [1, 2, 4, 5, 6, 10, 12, 18, 20, 29, 30, 36, 58, 60, 90, 116, 145, 174, 180, 290, 348, 371, 522, 580,  ...]
p=239: [1, 2, 4, 11, 22, 34, 36, 44, 65, 68, 69, 72, 119, 130, 138, 174, 238, 260, 348, 374, 476, 612,  ...]
p=241: [1, 2, 3, 4, 6, 11, 12, 22, 24, 33, 44, 50, 66, 100, 132, 150, 264, 300, 419, 545, 550,  ...]
p=251: [1, 2, 3, 5, 6, 9, 10, 11, 15, 22, 23, 25, 30, 32, 36, 45, 46, 50, 55, 64, 75, 96, 99, 100, 110, 115, 160, 180, 192, 198, 207, 225, 230, 253, 275, 300, 320, 352,  ...]
p=257: [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 50, 60, 80, 100, 120, 150, 174, 200, 240, 300, 348, 398, 400, 473,  ...]
p=263: [1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 21, 24, 25, 28, 30, 39, 42, 50, 56, 60, 75, 78, 84, 100, 120, 131, 150, 156, 168, 175, 195, 200, 210, 262, 273, 300, 312, 350, 390,  ...]
p=271: [1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 18, 20, 22, 28, 30, 33, 36, 42, 44, 45, 50, 55, 60, 66, 70, 84, 90, 100, 110, 126, 132, 135, 140, 150, 165, 180, 191, 198, 210, 220, 252, 270, 300, 308, 330, 350, 382,  ...]
p=277: [1, 3, 14, 33, 42, 46, 48, 65, 84, 92, 96, 138, 195, 276, 322, 336, 390, 528, 644,  ...]
p=281: [1, 2, 4, 23, 26, 35, 46, 70, 92, 140, 598, 805, 834, 910, 1610,  ...]
p=283: [1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 15, 18, 20, 24, 28, 30, 36, 40, 42, 47, 48, 56, 60, 69, 70, 72, 84, 90, 94, 96, 120, 138, 140, 141, 144, 168, 180, 188, 210, 235, 240, 276, 280, 282, 288, 336, 345, 360, 376,  ...]
p=307: [1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 48, 51, 56, 60, 69, 70, 84, 96, 102, 105, 120, 138, 140, 168, 204, 210, 240, 250, 255, 266, 276, 280, 336, 345, 357, 408, 420,  ...]
p=311: [1, 2, 3, 7, 9, 12, 18, 28, 35, 36, 42, 51, 63, 70, 84, 102, 105, 126, 140, 155, 204, 210, 252, 310, 315, 357, 420, 465, 630,  ...]
p=317: [1, 2, 3, 4, 5, 6, 10, 11, 12, 14, 15, 18, 20, 21, 22, 28, 30, 33, 36, 42, 44, 55, 60, 66, 69, 70, 84, 90, 105, 110, 126, 132, 138, 140, 154, 158, 165, 180, 198, 210, 220, 251, 252, 276, 308, 316, 330, 345, 396, 414, 420,  ...]
p=331: [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 24, 30, 36, 45, 48, 51, 60, 72, 90, 102, 120, 130, 144, 153, 180, 204, 240, 255, 260, 306, 329, 360, 390, 408, 441, 510,  ...]

T.Rex · 2023-03-02, 12:19

Here is the probably last result for $W_p$ prime:

Code:

p=347: [1, 5, 15, 23, 69, 115, 173, 345, 346]

p=313 and p=701 require too much computation.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness	GP2	Wagstaff PRP Search	414	2020-12-27 08:11
Basic Number Theory 18: quadratic equations modulo n	Nick	Number Theory Discussion Group	4	2017-03-27 06:01
Fermat number and Modulo for searching divisors	CyD	Factoring	4	2011-05-31 11:24
Wagstaff number primality test?	ixfd64	Math	12	2010-01-05 16:36
LLT Digraph	T.Rex	Math	26	2006-05-14 14:50

2023-01-10, 21:12	#2
T.Rex Feb 2004 France 1110101010₂ Posts	I forgot to talk about the universal seed for q-1 cycle found by kijinSeija: W(q-2). However, as paulunderwood has shown, it's the same as 1/4 mod Wq. And (3/2)^2-2 mod Wq = 1/4 Mod Wq. Note that kijinSeija also found that q^2 is a universal seed for Wagstaff under x2. Code: forprime(q=5,3539,w=(2^q+1)/3;s0=Mod(q^2,w);s=s0;for(i=1,q-1,s=Mod(s^2,w));if(s==s0,print(q)))

2023-01-16, 09:40	#3
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 11×557 Posts	How do the cycle lengths behave for other composite exponents? I wonder whether the proportion of very short cycle lengths could be different for composite exponents compared with prime exponents. If so, it may be possible to screen candidates based on checking a few random seeds for length. To check this, it shouldn't be necessary to calculate all the seeds for larger exponents. A random 1M would be enough(and make comparison easier without calculating %s) Would be happy to fiddle with your c code if you make it available. Is there any logic behind the missing cycle lengths? Looking at it, there seem to be patterns, but they often don't quite hold. Maybe this would be clearer for larger exponents?

2023-02-22, 17:14	#4
T.Rex Feb 2004 France 2×7×67 Posts	Another possible way to find Wagstaff ( $(2^q+1)/3$ PRPs, using a Cycle of length $q-2$ of the DiGraph under $x^2-2$ . Let: $S_n = S_{n-1}^2 -2 \ mod \ W_q$ . We have: $6 \ -> \ 34 \ -> \ 1154$ . It seems that: $W_q$ is (probably) prime iff $S_0=1154 \text{ and } S_{q-2}=S_0$ . Which is equivallent to say: $W_q$ is (probably) prime iff $S_0=6 \text{ and } S_{q}=1154$ . The following PARI/gp code checks the above test for all q primes from 11 to 127031. If the test is sucessful and q belongs to the list of known primes p such that $W_p$ is prime, then: "q +" is printed. If the test is sucessful and $W_q$ is NOT prime, then "q --" is printed. Code: L = [5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031] f(S0)={forprime(q=11,127031, W=(2^q+1)/3; S=S0; found=0; for(i=1,q-2, S=Mod(S^2-2,W)); if(lift(S)==S0, for(j=1,length(L), if(q==L[j],found=1;break)); if(found==1,print(q," +"),print(q," --"))))} f(1154) 13 + 17 + 19 + 23 + 31 + 43 + 61 + .... All known Wagstaff primes with $p>11$ are found, and none composite Wagstaff.

2023-03-02, 12:19	#7
T.Rex Feb 2004 France 938₁₀ Posts	Here is the probably last result for $W_p$ prime: Code: p=347: [1, 5, 15, 23, 69, 115, 173, 345, 346] p=313 and p=701 require too much computation.