Lucas-Lehmer sequences starting with s0 other than 4

[GP2]

The sequence used in the Lucas-Lehmer test is s₀ = 4, s_i = s_i−1² − 2.

Raphael Robinson, discoverer of the first Mersenne primes found by computer in the early 1950s (M521, 607, 1279, 2203, 2281), mentioned that "Alternatively, we may start with S₁ = 10; or, if n == 3 (mod 4), we may also use S₁ = 3." Some of the early hand-computed Mersenne calculations used a starting value of 3, for instance, H.S. Uhler finding M199 to be composite.

These alternative starting values are of no use for GIMPS in general because they produce residues completely different from the ones that you get with the conventional starting value of 4, unless you are verifying a Mersenne prime, in which case the residue will be zero as expected.

I tried to look up various proofs of the Lucas-Lehmer test, but couldn't really understand them, e.g., Terry Tao and a paper by John H. Jaroma. The latter mentions various variants but does not explicitly mention alternative starting values. Nor does the Wikipedia article.

There was an earlier discussion of this topic on this board itself many years ago, but it seemed inconclusive.

The Mersenne wiki mentions the OEIS sequence A018844 of possible starting values for Lucas-Lehmer sequences, including 4, 10, 52, 724, 970, etc. I tried these on very small Mersenne primes with a very simple program and they seemed to work.

I think it would be simple to alter the prime95/mprime source code just for fun, I believe the relevant line would be:

commonb.c

restart_test:	dbltogw (&lldata.gwdata, 4.0, lldata.lldata);

However, I haven't tried to compile the source yet.

My questions would be:

1) Is the idea of using alternative starting values (other than 4) mathematically sound?

2) When the next Mersenne prime is found, would there be any value in doing a verification run with a modified prime95/mprime program that uses a different starting value? This might be slightly superior to a normal verification run that merely uses a different shift count, because with a different starting value all the bits are entirely different at each iteration rather than the same bits merely being shifted. Naturally additional verification with cudaLucas or mlucas is still needed.

[Nick]

Originally Posted by GP2

1) Is the idea of using alternative starting values (other than 4) mathematically sound?

See Bas Jansen's PhD thesis:
http://www.math.leidenuniv.nl/scripties/PhDJansen.pdf

(The front matter and initial summary are in Dutch, but the main body of the document is in English.)

[retina]

Originally Posted by GP2

2) When the next Mersenne prime is found, would there be any value in doing a verification run with a modified prime95/mprime program that uses a different starting value? This might be slightly superior to a normal verification run that merely uses a different shift count, because with a different starting value all the bits are entirely different at each iteration rather than the same bits merely being shifted. Naturally additional verification with cudaLucas or mlucas is still needed.

But both the different shift value and a different starting value cause "all the bits [to be] entirely different at each iteration", so no difference there that I can see. But even so, there is still the need to use different software (and preferably different hardware architecture also) to verify. It would be terrible to have some weird and obscure P95 bug show prime for all shifts and/or starting values.when it actually isn't.

[axn]

P95 already supports alternate start values. See this post (and thread)

[science_man_88]

Originally Posted by GP2

The sequence used in the Lucas-Lehmer test is s₀ = 4, s_i = s_i−1² − 2.

you can also divide all even value starts by 2 ( that are used in x^2-2 versions) and have versions that use the step 2*x^2-1 that almost mimics what's done in mersenne TF I've even made pari code to do LL and TF with the same code using a flag but it's not fast.

[GP2]

Originally Posted by axn

P95 already supports alternate start values. See this post (and thread)

Ah, very nice. I hope it doesn't send the "residues from an alternate universe" to PrimeNet though.

I notice it's not documented, even in undoc.txt. Actually, even worktodo.add is undocumented, although it's mentioned in whatsnew.txt. Maybe we need an undocundoc.txt

[ATH]

Originally Posted by GP2

Ah, very nice. I hope it doesn't send the "residues from an alternate universe" to PrimeNet though.

I notice it's not documented, even in undoc.txt. Actually, even worktodo.add is undocumented, although it's mentioned in whatsnew.txt. Maybe we need an undocundoc.txt

It is probably best if most people do not know how to change the initialvalue since then we will start getting residue miss matches due to that. But the worktodo.add should be added to undoc.txt or readme.txt imo.

Did you see in that thread that there are 2 infinite series of initial values starting at 4 and 10:
A(1)=4, A(2)=52, A(N)=14*A(N-1)-A(N-2)
B(1)=10, B(2)=970, B(N)=98*B(N-1)-B(N-2)