Someone else’s conversation about Perrin pseudoprimes

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.



4 thoughts on “Someone else’s conversation about Perrin pseudoprimes

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s