In mathematics, the Perrin pseudoprimes are derived from the Perrin series of numbers.
The Perrin series is defined by the recurrence relation
- P(0) = 3, P(1) = 0, P(2) = 2,
and
- P(n) = P(n − 2) + P(n − 3) for n > 2.
The series begins
- 3 0 2 3 2 5 5 7 10 12 17 22 29 39 ... .
The numbers quickly become very large.
Consider n for which n divides P(n). Those are
- n = 1, 2, 3, 5, 7, 11, 13, ...
so initially 1 followed by prime numbers. It has been proved that for all primes p, p divides P(p).
The converse is not true; such composite numbers n are called Perrin pseudoprimes, and they are known to exist, the lowest being 271441.
External links
Institut für Medizinische Kybernetik und Artificial Intelligence]