In Someone else’s conversation about Perrin pseudoprimes and subsequent comments I linked to several posts by John D. Cook and Matt McIrvin on the subject of Perrin and other recurrence sequence pseudoprimes. There’s been enough development, including my own small contribution, that I want to summarize here, although I recommend the linked posts for additional details and further information.
Let’s start with the Lucas numbers L(n), defined by:
L(0) = 2
L(1) = 1
L(n) = L(n–2)+L(n–1) n>1
The Lucas numbers have the same recurrence relation as the more well known Fibonacci numbers F(n) but use a different starting sequence. There are some important connections between the two sequences, some of which I don’t entirely understand, but it’s interesting that in terms of the Golden Ratio ɸ = (1+√5)/2, F(n) = (ɸn–(–ɸ)–n)/√5 while L(n) = (ɸn+(–ɸ)–n).
The first several Lucas numbers, along with L(n) mod n (for n>1), are:
|L(n) mod n||–||–||1||1||3||1||0||1||7||4||3||1|
You can see that for n = 2, 3, 5, 7, and 11 — the prime numbers here — L(n) mod n = 1, while for the other values of n, L(n) mod n ≠ 1. Coincidence? Yes, and no. It can be proved that if n is prime, L(n) mod n = 1. On the other hand the converse is not true; if L(n) mod n = 1, n is not necessarily prime. Values of n which are composite but for which L(n) mod n = 1 are called Lucas pseudoprimes, and they are fairly few and far between. The smallest is 705, followed by 2465, 2737, and 3745. Clearly if L(n) mod n = 1 is probably prime.
Now consider the Perrin numbers. They’re defined by a similar recurrence relation and a starting sequence:
P(0) = 3
P(1) = 0
P(2) = 1
P(n) = P(n–3)+P(n–2) n>2
This sequence comes up in graph theory and was mentioned by R. Perrin in 1899. If you calculate P(n) mod n you find it equals 0 when n is prime. Again, you can prove this is true for all primes. And similarly to the Lucas numbers, for most composites, P(n) mod n ≠ 0, and similarly we have Perrin pseudoprimes, which are values of n for which n is composite and P(n) mod n = 0. But the Perrin pseudoprimes are far rarer than the Lucas ones. The smallest Perrin pseudoprime is 271,441, and it was not discovered until 1982; as recently as 1996, in Scientific American, Ian Stewart was writing (incorrectly) that no Perrin pseudoprimes were yet known, and that the smallest Perrin pseudoprime had a lower bound of 15 digits. Nowadays, of course, the computing power required to find the first Perrin pseudoprimes is readily available on your desktop. The trick to doing it fast is not to try to calculate the nth Perrin number and then divide by n; these numbers get very large very quickly, too large to be handled directly by most computer languages, and the time required is long. Instead, as McIrvin discusses, it’s best to convert the computation into a matrix exponentiation mod n, which can be done in logarithmic time and involves numbers not much larger than n. There are 17 Perrin pseudoprimes less than 1 billion.
As it turns out, any linear recurrence relation like the ones behind the Lucas and Perrin numbers can be used to generate a sequence for which the nth entry modulo n is equal to a particular value if n is prime. (This arises from a generalization of Fermat’s Little Theorem.) Then you have a corresponding set of pseudoprimes, where the nth entry modulo n has that same value even though n is composite.
McIrvin set his computer searching for sequences that produce particularly few pseudoprimes, and the best he found was:
M(0) = 5
M(1) = –1
M(2) = 3
M(3) = –7
M(4) = 11
M(n) = M(n–5)–M(n–3)+M(n–2)–M(n–1) n>4
(That initial sequence 5, –1, 3, –7, 11 may look arbitrary but in fact it’s determined by the form of the recurrence relation. Again, see the previously linked posts for more.) In this case the prime numbers satisfy M(n) mod n = n–1. Composite numbers satisfying that relation might as well be called McIrvin pseudoprimes, and the smallest of them is … (drum roll please) … 4. All right, that one is kind of small! But the second McIrvin pseudoprime is 14,791,044. It took McIrvin a while to find the third one: 143,014,853. At this point he stopped searching and I started, finding the rest of the McIrvin pseudoprimes less than 1 billion: 253,149,265; 490,434,564; 600,606,332; and 993,861,182. Seven in all, and note that of those, five are even and one is divisible by 5. The only one that’s not obviously composite is 143,014,853 = 907 x 157,679.
So if someone gives you an n in the range 2 to 999,999,999, you can compute M(n) mod n, see if it equals n–1, and thereby determine if n is prime… with a 7 / 999,999,998 chance of being wrong. And that’s only if you don’t examine the last digit of n.