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.

 

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s