# Perrin sequence

The Perrin sequence is the sequence of integers defined by the recurrence relation *P*(*n*)
= *P*(*n* - 2) + *P*(*n* - 3), with the initial conditions *P*(0) = 3, *P*(1) = 0, *P*(2) = 2. Although the sequence
is named after R. Perrin who studied it in 1899, it had been explored earlier,
in 1876, by Édouard Lucas.

As in the case of the similar Padovan sequence, the ratio of consecutive
Perrin numbers tends toward the plastic number.
More importantly, it has been shown that *n* divides *P*(*n*)
exactly if *n* is a prime number. For
example, 19 is prime, *P*(19) = 209 and 209/19 = 11. The first few
Perrin primes (Perrin numbers that are prime) are: 2, 3, 5, 7, 17, 29, 277,
367, 853.

Lucas conjectured that *only* when the divisor is prime is the result
a prime, which would mean that the Perrin sequence could be used as a test
for non-primality, i.e., any number *n* that did not divide *P*(*n*)
would be composite. However this conjecture is now known to be false. There
are indeed composite numbers, known as **Perrin pseudoprimes**,
which will divide the corresponding Perrin numbers to give whole numbers.
The first and smallest Perrin pseudoprime, 271441, was found by William
Adams and Daniel Shanks in 1982, and it was subsequently proved that there
are an infinite number of them.