[seqfan] Lucas-Lehmer pseudoprimes

[David Wilson]

The Lucas-Lehmer test is

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

for odd prime p.

It turns out that

     A003010(n) = A003500(2^n)

so we have

     2^p-1 is prime iff A003500(2^(p-2)) == 0 (mod 2^p-1)

Letting k = 2^(p-2), gives

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

If we ignore the known form of k, this test seems to work for small k == 
2 (mod 6).
This leads to the generalized Lucas-Lehmer primality test

[1]    A003500(6k+2) == 0 (mod 24k+7)

This devolves to the Lucas-Lehmer test for Mersenne primes when 24k+7 = 
2^p+1 for odd prime p.

Empirically, for n = 24k+7, [1] appears to be true for prime n and a few 
composite n (pseudoprimes).
I was able to find the following Lucas-Lehmer pseudoprimes:

Lucas-Lehmer psuedoprimes: Composites n == 7 (mod 24) with 
A003500((n+1)/4) == 0 (mod n)

1 1037623
2 2211631
3 4196191
4 7076623
5 9100783
6 11418991
7 15219559
8 21148399
9 29486239
10 32060503
11 36035383
12 56902999
13 64450063
14 69017023
15 112367863
16 134793031
17 184353679
18 211883743
19 243005527
20 287903431
21 365603743