Perrin Pseudoprimes
May 29, 2015
The Perrin Numbers Pn are defined as P0 = 3, P1 = 0, P2 = 2, and Pn+3 = Pn+1 + Pn for n > 2. If Pn (mod n) ≡ 0, then n is most likely prime. Perrin’s formula always reports that a prime number is prime, but sometimes reports a composite number is prime, though seldom: there are only two pseudoprimes, 271441 and 904631, less than a million.
The Perrin sequence A001608 is computed by sequential addition. An individual member of the Perrin sequence can be computed by matrix exponentiation followed by matrix multiplication:
![P_n = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right] ^n \left[ \begin{array}{c} 3 \\ 0 \\ 2 \end{array} \right]](https://s0.wp.com/latex.php?latex=P_n+%3D+%5Cleft%5B+%5Cbegin%7Barray%7D%7Bccc%7D+0+%26+1+%26+0+%5C%5C+0+%26+0+%26+1+%5C%5C+1+%26+1+%26+0+%5Cend%7Barray%7D+%5Cright%5D+%5En+%5Cleft%5B+%5Cbegin%7Barray%7D%7Bc%7D+3+%5C%5C+0+%5C%5C+2+%5Cend%7Barray%7D+%5Cright%5D+&bg=ffffff&fg=555555&s=0&c=20201002)
The terms of the Perrin sequence grow exponentially at a rate of 1.32471795, which is known at the plastic number.
The Perrin pseudoprimality test can be implemented using matrix exponentiation followed by matrix multiplication with all operations performed modulo n. Sloane gives a list of Perrin pseudoprimes at A013998.
Your task is to write a function to determine if a number is a Perrin pseudoprime and to find all Perrin pseudoprimes less than a million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 