[seqfan] Lucas-Lehmer constant and other ramblings
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).
A003010(n) = z
c^(2^n) + c^(-2^n) = z
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
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)?
More information about the SeqFan