Perrin Sequence

The Integer Sequence defined by the recurrence

$$P(n)=P(n-2)+P(n-3)$$ (1)

with the initial conditions $P(0)=3$, $P(1)=0$, $P(2)=2$. The first few terms are 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, ... (Sloane's A001608). $P(n)$ is the solution of a third-order linear homogeneous Difference Equation having characteristic equation

$$x^3-x-1=0,$$ (2)

discriminant $-23$, and Roots

$$\alpha \approx 1.324717957$$ (3)

$$\beta \approx -0.6623589786+0.5622795121i$$ (4)

$$\gamma \approx -0.6623589786-0.5622795121i.$$ (5)

The solution is then

$$A(n)=\alpha^n+\beta^n+\gamma^n,$$ (6)

where

$$A(n)\sim \alpha^n.$$ (7)

Perrin (1899) investigated the sequence and noticed that if $n$ is Prime, then $n\vert P(n)$. The first statement of this fact is attributed to É. Lucas in 1876 by Stewart (1996). Perrin also searched for but did not find any Composite Number $n$ in the sequence such that $n\vert P(n)$. Such numbers are now known as Perrin Pseudoprimes. Malo (1900), Escot (1901), and Jarden (1966) subsequently investigated the series and also found no Perrin Pseudoprimes. Adams and Shanks (1982) subsequently found that 271,441 is such a number.

See also Padovan Sequence, Perrin Pseudoprime, Signature (Recurrence Relation)

References

Adams, W. and Shanks, D. ``Strong Primality Tests that Are Not Sufficient.'' Math. Comput. 39, 255-300, 1982.

Escot, E.-B. ``Solution to Item 1484.'' L'Intermédiare des Math. 8, 63-64, 1901.

Jarden, D. Recurring Sequences. Jerusalem: Riveon Lematematika, 1966.

Perrin, R. ``Item 1484.'' L'Intermédiare des Math. 6, 76-77, 1899.

Stewart, I. ``Tales of a Neglected Number.'' Sci. Amer. 274, 102-103, June 1996.

Sloane, N. J. A. Sequence A001608/M0429 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.