Perrin number

The Perrin numbers are defined by the recurrence relation

$P_{n}:={\begin{cases}3&{\mbox{if }}n=0;\\0&{\mbox{if }}n=1;\\2&{\mbox{if }}n=2;\\P_{n-2}+P_{n-3}&{\mbox{if }}n>2.\\\end{cases}}$

The first few numbers of the sequence are: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, ...

Properties

A special property of the sequence of Perrin numbers is, that if $p\$ is a prime number, then $p\$ divides $P_{p}\$. The converse is false, because there exist composite numbers $q\$ which divide $P_{q}\$. Those numbers $q\$ are called Perrin pseudoprimes. The first few Perrin pseudoprimes are: 271441, 904631, 16532714, 24658561, 27422714, ...