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.