Perrin's Sequence 

Define the sequence of integers by the linear recurrence formula 

_{} 

with the initial values s_{0} = 3, s_{1} = 0, s_{2} = 2. This sequence was discussed by Edouard Lucas in 1878 (American Journal of Mathematics, vol 1, page 230ff), who noted that if p is a prime then p divides s_{p}. This is an immediate consequence of Fermat's Little Theorem, and as such is a necessary but not sufficient condition for primality (see proof). Subsequently (1899) the same sequence was mentioned by R. Perrin (L'Intermediaire Des Mathematiciens). The most extensive (published) treatment of this sequence was given in an excellent paper by Dan Shanks and Bill Adams in 1982 (Mathematics of Computation, vol 39, n. 159). Shanks and Adams referred to this as Perrin's sequence. 

This sequence has many interesting properties, making it, in some ways, more remarkable than the Fibonacci sequence. For example, most people are familiar with the spiral of equilateral squares whose edge lengths correspond to the Fibonacci numbers, but less wellknown is the spiral of equilateral triangles shown below described in Spiral Tilings and Integer Sequences. 


The edge lengths of successive triangles in this spiral satisfy the Perrin recurrence s_{n} = s_{n}_{2} + s_{n}_{3} as well as the recurrence s_{n} = s_{n}_{1} + s_{n}_{5}, as is apparent from the above figure. This can be seen as a consequence of the fact that the characteristic polynomial of Perrin's sequence, x^{3}  x  1, is a divisor of the characteristic polynomial of the 5th order sequence, i.e., 

_{} 

The real root r of x^{3}  x  1 has the nice expression as a sequence of nested cube roots: 

_{} 

If we define the angle q in terms of this root r as 

_{} 

then the terms of the Perrin sequence can be expressed in closed form as 

_{} 

In fact, with the appropriate provisos, we can replace n with any complex argument z to define Perrin's function on the complex plane, as shown in the figure below for real components from 5 to 15 and imaginary components from 5 to +5. 


White indicates regions where both the real and imaginary components are positive, black where both are negative, and the two shades of gray where one is positive and the other negative. The zeros of this function are all on the real axis in the left halfplane, whereas there are two sets of complex conjugate zeros on the right halfplane (at points where all four shades meet). 

Obviously, for any positive prime p and any integer n we have 

_{} 

so in particular we have 

_{} 

In addition, for any integers m,n,k we have the relation 

_{} 

Which is really just a special case of a much more general class of relations satisfied by any linear recurring sequence. (See the note Identities for Linear Recurring Sequences.) In this particular case we have relations like 

_{} 

and so on, as well as 

_{} 

Using these relations for s_{2n} and s_{2n+1} gives an efficient means of computing s_{k} via the usual binary pattern algorithm on the plus and minus sides of the sequence. This same twosided approach can be extended to higher order recurrences, but it quickly becomes more practical to use the more general onesided relations (described in the note mentioned above). 

Perrin's sequence also has the interesting property that its terms are cumulative sums of the sequence itself, i.e., we have s_{1} = 0 and 

_{} 

The terms of Perrin's sequence can also be expressed as a function of binomial coefficients, leading to many interesting results. For example, it's possible to deduce that the summation 

_{} 

is an integer for N=2755452, and for no smaller N. (See the note Summations and Recurrences.) 

As a compositeness test, Perrin's sequence is much stronger than the typical 2nd order Lucas sequence. For example, the smallest symmetric pseudoprime relative to the Fibonacci quadratic x^{2} – x – 1 is 705, whereas the smallest relative to Perrin's cubic x^{3} – x – 1 is 

_{} 

as found by Shanks and Adams (using an HP41C calculator). Subsequently Shanks, G. Kurtz, and H. Williams tabulated all the symmetric pseudoprimes relative to Perrin's sequence less than 50(10)^{9}. They noted that none of these pseudoprimes had the signature of a prime p such that Perrin's polynomial is irreducible (mod p). As far as I know the question of whether such a pseudoprime exists is still open. 

Further discussion of pseudoprimes relative to various polynomials can be found in the notes 

