[seqfan] Lucas-Lehmer constant and other ramblings

[David Wilson]

The Lucas-Lehmer test is

     2^n-1 is prime iff A003010(n-2) == 0 (mod 2^n-1)

for odd n.

The connection between the Lucas-Lehmer test and the constant c = 
2+sqrt(3) is well known, specifically the identity

     A003010(n) = c^(2^n) + c^(-2^n)

(Note: The Sillcox formula on A003010 is incorrect, perhaps because the 
sequence was subsequently reindexed).

Now suppose

     A003010(n) = z

that is

     c^(2^n) + c^(-2^n) = z

Squaring gives

     c^(2^(n+1)) + 2 + c^(-2^(n+1)) = z^2
     => c^(2^(n+1)) + c^(-2^(n+1)) = z^2 - 2.
     => A003010(n+1) = z^2 - 2.

This proves the Lucas-Lehmer recurrence A003010(n+1) = A003010(n)^2 - 2

Letting the "Helms constant" be h = ln(c) (Helms actually gave h/4), we get

     A003010(n) = e^(h*2^n) + e^(-h*2^n) = 2 cosh(h*2^n)

I think that any interesting connections between h and the Lucas-Lehmer 
test would follow from this identity.

In terms of h, the Lucas-Lehmer test takes on the interesting form

     2^n-1 is prime iff cosh(h*2^n) == 0 (mod 2^n-1)

There are also interesting connections to sequence

     A003500(n) = c^n + c^-n = e^(hn) + e^(-hn) = 2 cosh(hn)

The formula c^n + c^-n is an explicit formula for a linear recurrence 
with characteristic polynomial

     p(x) = (x - c)(x - c^1)  =  x^2 - (c + c^-1) x + 1

But we have

     A003500(1) = c + c^-1 = 4

So

     p(x) = x^2 - 4x + 1.

This characteristic polynomial yields the linear recurrence for A003500:

     A003500(n+2) - 4*A003500(n+1) + A003500(n) = 0.

We also note that

     A003010(n) = A003500(2^n)

(there is a verbose %C comment to this effect on A003010, which might be 
replaced with the above simple %F formula).

In terms of A003500, the Lucas-Lehmer test is

     2^n-1 is prime iff A003500(2^(n-2)) == 0 (mod 2^n-1) (n >= 3)

Letting k = 2^(n-2), this becomes

     4k-1 is prime iff A003500(k) == 0 (mod 4k-1).

Ignoring for a moment that k must be a power of 2, this generalized 
Lucas-Lehmer test seems to work for k == 2 (mod 6). Can anyone find an 
exception (a Lucas-Lehmer pseudoprime)?