 mersenneforum.org DiGraph under x^2-2 modulo a Wagstaff number
 Register FAQ Search Today's Posts Mark Forums Read 2023-01-10, 18:11 #1 T.Rex   Feb 2004 France 3×311 Posts DiGraph under x^2-2 modulo a Wagstaff number 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 ? Last fiddled with by T.Rex on 2023-01-10 at 18:17   2023-01-10, 21:12 #2 T.Rex   Feb 2004 France 11101001012 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) 603310 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?  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post GP2 Wagstaff PRP Search 414 2020-12-27 08:11 Nick Number Theory Discussion Group 4 2017-03-27 06:01 CyD Factoring 4 2011-05-31 11:24 ixfd64 Math 12 2010-01-05 16:36 T.Rex Math 26 2006-05-14 14:50

All times are UTC. The time now is 15:44.

Tue Feb 7 15:44:51 UTC 2023 up 173 days, 13:13, 1 user, load averages: 1.39, 1.46, 1.27