20160107, 02:40  #1 
"J. Gareth Moreton"
Feb 2015
Nomadic
2·3^{2}·5 Posts 
Erroneous values of s_n?
Just to clarify, I'm referring to the value of 's_{n}' that is calculated in each iteration of the LucasLehmer Primality Test (and which s_{p2} mod 2^{64} is the residue stored in the GIMPS database).
Mostly out of curiosity but also for mathematics and programming practice, I'm analysing the algorithm used to test Mersenne numbers, but it got me thinking, just from logical reasoning: There seem to be certain values of s_{n} (mod 2^{p}  1) that, if they appear, indicate a composite Mersenne number at best or an error of some kind at worst:
Maybe I'm overthinking this, but do these values ever appear in practice, either as a hardware/mathematical error or as part of a sequence, and if so, how should they be handled? 
20160107, 02:51  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160107 at 03:18 

20160107, 07:39  #3 
Einyen
Dec 2003
Denmark
31·101 Posts 
The residue 2 has happened several times when the partial residue during the run turns to 0 due to a hardware error then it will go 0, 2, 2, 2, 2... and end in 2.
Here is one example: http://mersenne.org/M38273689 Here is most likely another 2 that has not been verified yet: http://mersenne.org/M79060367 
20160107, 11:29  #4 
"J. Gareth Moreton"
Feb 2015
Nomadic
132_{8} Posts 
I can see how checking the value of s_{n} during every iteration is costprohibitive, but would it be an idea to check for a value of 2 and 1 every so often, like how rounding is currently performed? It might save some wasted testing (and mark the result as Suspect after it attempts to go back to correct itself)? I assume there haven't been any cases where a residue of 2 is reproducible and verified yet.
s_{n} = 4 I can see not being an error, but a special situation of the primality test. I would like to find an example where it appears in practice though. Last fiddled with by CuriousKit on 20160107 at 11:29 
20160107, 13:25  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160107 at 13:42 

20160107, 17:43  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3×1,571 Posts 

20160107, 21:17  #7 
"J. Gareth Moreton"
Feb 2015
Nomadic
2×3^{2}×5 Posts 
Fascinating. Thanks for the headsup. I had a feeling quadratic residues/nonresidues had something to do with it.
Sorry for the naïve question, but how is K defined here? I can see that 75, 147 and 363 are equal to 3 * a prime square, but 91 is an odd one out here. I'm trying to figure out in my head what stops 2, 0 (when n < p  2) and 2 from appearing. I'm assuming that, for 2, the only values that equate to it are 2 and 2 itself, and 0 is what creates 2 (and I think this is the only value because the only solution to "s_{n}^{2} ≡ 0 (mod 2^{p}  1)" is zero, since the modulus cannot be a perfect square). I swear I could go insane trying to get my head around all of this, but I'm going to try! 
20160129, 13:26  #8 
"Jeppe"
Jan 2016
Denmark
2^{3}×3×7 Posts 
Let $p$ be an odd prime ($M=2^p1$ is possibly composite), and $s_n$ be defined as above.
If we consider the infinite sequence: $$s_0 \mapsto s_1 \mapsto s_2 \mapsto s_3 \mapsto \dots \pmod{2^p1}$$ then clearly it will become periodic at one point. For there are only finitely many possible values in $\mathbb{Z}/M\mathbb{Z}$, and as soon as we hit a value we have seen before, we go into a loop. So the question is if it can ever happen for some rare values of $p$ that this becomes periodic before $s_{p2}$. So is there any $p$ which admits two indices $0 \le i < j \le p2$ such that $s_i \equiv s_j \pmod{2^p1}$? Can anybody answer that? /JeppeSN 
20160129, 14:44  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16EE_{16} Posts 
Quote:


20160129, 15:11  #10  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:
Last fiddled with by science_man_88 on 20160129 at 15:15 

20160131, 05:39  #11 
Romulan Interpreter
Jun 2011
Thailand
24E5_{16} Posts 
No.
There can't be a cycle with the period smaller than 2p. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Timing for different B1 values?  CRGreathouse  GMPECM  8  20180512 05:57 
reserving a few k values  Trilo  Riesel Prime Search  7  20150927 23:20 
Erroneous data  ATH  Data  8  20131113 19:21 
reserving a few k values  Trilo  Riesel Prime Search  0  20130825 14:47 
B1/B2 values  esakertt  Information & Answers  2  20121114 13:11 