The Perrin numbers have a definition analogous to Fibonacci numbers. Define P0 = 3, P1 = 0, and P2 = 2. Then for n > 2, define
Pn+3 = Pn+1 + Pn+0.
It appears that n is prime “almost if and only if” Pn mod n = 0.
The “only if” condition is true without qualification: if n is prime, Pn mod n = 0. It’s the “if” part that’s almost true. When Pn mod n = 0, n is usually prime. Composite numbers that satisfy the Perrin condition Pn mod n = 0 are called Perrin pseudoprimes. The smallest Perrin pseudoprime is 271,441. The next is 904,631.
There are only 17 Perrin pseudoprimes less than a billion. By comparison, there are 50,847,534 primes less than a billion.
So if you used the Perrin condition to test whether numbers less than a billion are prime, you would correctly identify all 50,847,534 primes as primes. But out of the 949,152,466 composite numbers, you would falsely report 17 of these as prime. In other words, you would be 100% accurate in identifying primes as primes, but only 99.999998% accurate in identifying composite numbers as composite.
From Wikipedia: “The question of the existence of Perrin pseudoprimes was considered by Perrin himself, but it was not known whether they existed until Adams and Shanks (1982) discovered the smallest one, 271441 = 5212.”
Discovered in 1982. I was able to reproduce this result in a few minutes messing around on my computer. It’s amazing how much better the tech available to the masses has gotten.
(That expression should be 521^2, of course.)
Is it weird that this post gave me “that-is-so-cool” chills?
The result does seem to come out of nowhere.
One way to see that n|Pn when n is prime:
The solution to “almost” any recurrence of this sort has the form Pn = A.a^n + B.b^n + C.c^n where a,b,c are the roots of the polynomial corresponding to the recurrence, in this case x^3-x-1. For this particular choice of starting values, we have A=B=C=1; in other words, Pn is just the sum of the n’th powers of the roots of that polynomial.
Now suppose p is prime and work in some extension of Z/pZ in which the polynomial splits completely. That’s a field of characteristic p, and any such field has an automorphism called the “Frobenius map” (or Frobenius endomorphism, or Frobenius automorphism), taking x to x^p. (The guts of why it’s an automorphism: because (x+y)^p = x^p+y^p, because all the other terms in the binomial expansion have coefficients that are multiples of p.)
The elements of Z/pZ themselves are left alone by the Frobenius map, which means that if a,b,c are the roots of our polynomial then a^p, b^p, c^p are also roots of that polynomial; automorphisms are necessarily bijective, so a^p, b^p, c^p are in fact a,b,c in some order. So, in particular, a^p+b^p+c^p = a+b+c = 0. In other words, P_p = 0 (mod p).
All of this generalizes somewhat. You can use any monic polynomial without repeated factors; the condition isn’t necessarily n|Pn, but rather Pn=P0 (mod n), and actually there are some other easily-checked things that are always true when n is prime and that you should probably build into the definition of “pseudoprime” when conducting this sort of test. The degree doesn’t have to be 3. (One simple case of degree 2 gets you the Lucas-Lehmer primality test.) You always get infinitely many “pseudoprimes”.
There are some very nice papers by Jon Grantham about this stuff, at least some of which you can find on the web.
Whoops! Not the Lucas-Lehmer test (which applies only to Mersenne numbers and tells you absolutely for sure whether they’re prime) nor the Lucas test (which applies to any number but is only any use when you’ve already factorized n-1) but a test that doesn’t have a special name, but whose counterexamples are called Lucas pseudoprimes.
My apologies for the error.
Thanks g, that was interesting and nicely presented.
Shouldn’t the formula be defined for n >= 0?