Erroneous values of s_n?

[JeppeSN]

Originally Posted by LaurV

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

Of course if $2^p-1$ is actually prime, we end up with the cycle $\dots \mapsto 0 \mapsto -2 \mapsto 2 \mapsto 2 \mapsto \dots\pmod{2^p-1}$ whose length ($1$) is clearly smaller than $2p$.

So I take your statement as referring to the case where $M$ is composite. Is it trivial to see that the eventual period is at least $2p$ in that case?

As an example, with $p=29$ (whose Mersenne number $536870911$ is composite), the first time $s$ repeats itself, is $s(1)=s(253)$, and of course $s(1)$ is $14\pmod{536870911}$, so the period is $252$ in this case.

/JeppeSN

[LaurV]

Yes. Composite p. I was answering to your post, not to sm88's intervention.
Actually, the minimum period that can be is 3p, if I am not mistaken. If you have a cycle, then you have some x^2-2=y^2-2 for different x and y, because there is no x^2=6 (mod Mp). That means there are terms before the loop starts (like in the "rho" method, the infinite string that you painted in your post looks like the Greek letter rho - then you take the two terms that enters the loop of the rho, they are different). That means (x+y)(x-y) is a proper factorization of Mp (mod Mp), and because Mp is 7 (mod 8) then one of the terms and only one, is 7 (mod 8). Therefore y is an odd multiple of p. Ex: for 2^11-1 you have (56+33)(56-33).

[axn]

It would seem that the period is a multiple of p-1.

[JeppeSN]

Originally Posted by LaurV

Yes. Composite p. I was answering to your post, not to sm88's intervention.
Actually, the minimum period that can be is 3p, if I am not mistaken. If you have a cycle, then you have some x^2-2=y^2-2 for different x and y, because there is no x^2=6 (mod Mp). That means there are terms before the loop starts (like in the "rho" method, the infinite string that you painted in your post looks like the Greek letter rho - then you take the two terms that enters the loop of the rho, they are different). That means (x+y)(x-y) is a proper factorization of Mp (mod Mp), and because Mp is 7 (mod 8) then one of the terms and only one, is 7 (mod 8). Therefore y is an odd multiple of p. Ex: for 2^11-1 you have (56+33)(56-33).

Very interesting. I try to actually do this for $p=11$ as you suggest. I find that the first value that is repeated is $s(1)=14\pmod{2047}$ which equals $s(61)$. (The period is $60$ here.) But the predecessor $s(60)$ is $441 \pmod{2047}$, so at first the factorization I get is:

$$(441-4)(441+4)=437 \cdot 445 \equiv 0 \pmod{2047}$$

So I can agree this zero product shows $2047$ is not prime (we have zero divisors in the ring).

/JeppeSN

[JeppeSN]

The first case where the initial part before the loop consists of more than one term, is $p=37$ (so $M=137438953471$). We get:

s(0)=4
s(1)=14
s(2)=194
s(3)=37634
s(4)=1416317954 <-- predecessor to loop, not seen again
s(5)=111419319480 <-- will be seen again, start of loop
s(6)=75212031451
s(7)=42117743384
s(8)=134212256520
...
s(516924)=128698515666
s(516925)=127095751061
s(516926)=125728907914
s(516927)=75807173405
s(516928)=13742681494 <-- last in loop; other predecessor to 111419319480
s(516929)=111419319480 <-- revisiting
s(516930)=75212031451
s(516931)=42117743384
s(516932)=134212256520
...

Again the period length $516924$ is a multiple of $37-1$.

/JeppeSN