Erroneous values of s_n?

[CuriousKit]

Just to clarify, I'm referring to the value of 's_n' that is calculated in each iteration of the Lucas-Lehmer Primality Test (and which s_p-2 mod 2⁶⁴ 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:

• 4 (when n != 0) - if reproducible, the residues form a sequence of period n, and the final residue, which is definitely not zero, can be deduced without actually completing all the iterations, as s_p-2 = s_{(p-2) [B]mod[/B] n}.
• 2 - s_n+1 will also equal 2 as a result, and by induction will never leave this value.
• 1 - next value is -1, which never changes.
• -1 (or 2^p - 2) - as with 2, this value never changes in subsequent iterations.
• -2 (or 2^p - 3) - next value is 2, which never changes.
• 0 (if n != p - 2) - next value is -2, which in turn becomes 2 and then never changes.

Maybe I'm over-thinking 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?

[science_man_88]

Originally Posted by CuriousKit

Just to clarify, I'm referring to the value of 's_n' that is calculated in each iteration of the Lucas-Lehmer Primality Test (and which s_p-2 mod 2⁶⁴ 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:

• 4 (when n != 0) - if reproducible, the residues form a sequence of period n, and the final residue, which is definitely not zero, can be deduced without actually completing all the iterations, as s_p-2 = s_{(p-2) [B]mod[/B] n}.
• 2 - s_n+1 will also equal 2 as a result, and by induction will never leave this value.
• 1 - next value is -1, which never changes.
• -1 (or 2^p - 2) - as with 2, this value never changes in subsequent iterations.
• -2 (or 2^p - 3) - next value is 2, which never changes.
• 0 (if n != p - 2) - next value is -2, which in turn becomes 2 and then never changes.

Maybe I'm over-thinking 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?

the case of 4 can be technically any value the sequence takes on that will get that behaviour in theory as the value squared mod the mersenne number then mod 2^64 has either already appeared or the test functions as normal. but that's harder to code efficiently for than the cases of -1,2,and 4 sometimes checking is the inefficient way to code it because if the check takes more time than is needed to complete the test then it becomes faster to complete the test anyways and throw an error at the end I think, but I'm not sure how it's coded for GIMPS. someone more knowledgeable will come along soon I bet. edit: squared minus 2

[ATH]

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

[CuriousKit]

I can see how checking the value of s_n during every iteration is cost-prohibitive, 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.

[science_man_88]

Originally Posted by CuriousKit

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.

okay all mersenne numbers with odd exponents>1 fall into 7 or 31 mod 120 and all values in A003010>14 fall into 74 mod 120. 120*x+74 only has remainder 4 by 120*y+31 for x=(10*y+2) mod 120*y+31 and for 120*y+7 for y=0;x=7 but for y>0; x=10*y mod (120*y+7) from what I've tested. now it's as simple as finding the values x takes on in A003010 and you'll have your case. edit: okay technically you need to know the y values mersennes take on as well but both are relatively simple at last check then it's just checking for a conditions.

[Batalov]

Originally Posted by CuriousKit

....an error of some kind at worst:

• 4 (when n != 0) :
  cannot be in sequence, because there is no s_n-1 such that s_n-1² = 6; 6 is QNR (quadratic non-residue).
• same is true for all 3*2ⁿ-2 (OEIS seq A033484 ): 1, 4, 10, 22, 46, 94, 190, 382, 766, ...
• But not only these values: Any 3^odd*2ⁿ-2 also can never be a member of the sequence
• Any K*2ⁿ-2, where K=75, 91, 147, 363...

[CuriousKit]

Fascinating. Thanks for the heads-up. I had a feeling quadratic residues/non-residues 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² ≡ 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!

[JeppeSN]

Let $p$ be an odd prime ($M=2^p-1$ 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^p-1}$$
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_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$?

Can anybody answer that?

/JeppeSN

[henryzz]

Originally Posted by JeppeSN

Let $p$ be an odd prime ($M=2^p-1$ 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^p-1}$$
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_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$?

Can anybody answer that?

/JeppeSN

I pretty certain not if it is a Mersenne prime.

[science_man_88]

Originally Posted by JeppeSN

Let $p$ be an odd prime ($M=2^p-1$ 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^p-1}$$
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_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$?

Can anybody answer that?

/JeppeSN

well if it doesn't loop back to 4 that means k*Mp is the difference of two squares aka it can be expressed as which if I remember correctly from fermat's method means it can be factored into (a-b)(a+b) so one of these two has to divide by the mersenne number or one of it's factors itself. the other cases are if it loops back to 4, and when it goes to one of the values listed in which case it goes to repeat again and again with period 1. I'm not smart enough to go further into this so I'll leave the rest to someone smarter.

[LaurV]

No.
There can't be a cycle with the period smaller than 2p.