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.

Advertisements

Also https://plus.google.com/100452847199780289157/posts/1Mtdckt1mm4 and https://plus.google.com/100452847199780289157/posts/HNS1LYyTnpT.

And THIS! https://plus.google.com/u/0/100452847199780289157/posts/K7NSbA3LjA1

That latest sequence is now in OEIS.