A Mersenne Coincidence

The well known Fibonacci numbers give the edge lengths of successive 
squares in an spiral composed of an infinite sequence of geometrically 
increasing squares that tile the plane.  There is a sequence of 
integers that corresponds to the edge lengths of equilateral triangles 
in a geometric spiral that tiles the plane.  This sequence satisfies 
the characteristic recurrence

               s(n)  =  s(n-2)  +  s(n-3)

The sum of the nth powers of the roots of x^3-x-1 satisfy this 
recurrence, and the first few values are shown below:

                      n      s(n)
                    -----  --------
                      0       3
                      1       0
                      2       2
                      3       3
                      4       2
                      5       5
                      6       5
                      7       7
                      8      10
                        etc.

This is a convenient sequence for primality testing, because for any 
prime p, the term s(p) is divisible by p.  In contrast, if n is 
composite, then s(n) is *almost* never divisible by n.  The smallest 
pseudoprime (i.e., composite n that divides s(n)) is 271441 = (521)^2.  
(This was first discovered by Shanks and Adams in 1982 Mathematics 
of Computation).  The only other pseudoprime of this type less than 
1 million is 
                    904631 = (7)(13)(9941).

Oddly enough, each of the prime divisors of these pseudoprimes (7, 13, 
521, and 9941) is a Mersenne exponent, i.e., a prime p such that 
2^p - 1 is prime.  Although I can't think of any reason that Mersenne 
exponents should be preferred as factors of pseudoprimes, this 
numerical coincidence made me curious to know the next composite n 
that divides s(n).  It turns out the next one is over 16 million:

              16532714 = (2)(11)(11)(53)(1289)

Well, this not only demolishes any goofy notions about Mersenne 
exponents, it also gives an example of an *even* pseudoprime.  Just 
for good measure, the next composite n that divides s(n) is

                 24658561 = (19)(271)(4789)

By the way, it's not hard to show that the elements of the s(k) 
sequence have the closed form expression

                               N     (2N+k+a+b-1)!
          s(6N+r)  =  (6N+r) SUM  -------------------
                              k=0  (2N-2k+a)! (3k+b)!

where r=0,1,2,3,4, or 5, and a,b are the least non-negative integers 
such that a=r (mod 2) and b=-r (mod 3).  Clearly the summation is an 
integer if and only if s(6N+r) is divisible by (6N+r).  Since we've 
seen that 6*2755452 + 2  is the smallest pseudoprime of the form 6N+2, 
it follows that the number 2755452 is the smallest value of N such 
that the summation 

                    N       (2N+k)!
                 SUM     ---------------- 
                   k=0   (2N-2k)! (1+3k)!

is an integer.

It's worth noting that the requirement s(n)=0 (mod n) is really only 
half of the full pseudoprime test based on x^3-x-1.  The other half 
is s(-n)=-1 (mod n).  When this is imposed, the complete smallest 
pseudoprime relative to x^3-x-1 is

                    27664033 = (3037)(9109)

which was also first discovered by Shanks and Adams.