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.




I’ve been looking at Scratch, a simple visual programming language. Fun stuff. Here’s output from a program that draws dragon curves:

and here’s a Paterson’s worm:

An extension of Scratch called BYOB (Build Your Own Blocks) looks interesting.