# [seqfan] Lucas-Lehmer constant and other ramblings

David Wilson davidwwilson at comcast.net
Sun Apr 8 03:58:13 CEST 2012

```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)?

```