The Perrin numbers *P(n)*, defined by a simple recurrence relation, have the fascinating property that *P(n)* mod *n* = 0 if and “almost only if” *n* is prime. That is, the relation is true if *n* is prime, and if *n* is composite it is almost always not true; the smallest composite *n* for which *P(n)* mod *n* = 0 (the smallest *Perrin pseudoprime*) is 271,441.

John D. Cook wrote a blog post about Perrin pseudoprimes. Matt McIrvin responded with a post about computing them. John D. Cook responded to that with some more on the subject.

I have nothing to add, just wanted to point that blog conversation out. Worth a read.

### Like this:

Like Loading...