Perrin pseudoprimes

The column Mathematical Recreations by Ian Stewart in the June issue of Scientific American discusses the Perrin sequence A(n) with:
A(0)=3, A(1)=0, A(2)=2, A(n+1)=A(n-1)+A(n-2)
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A(n) 3 0 2 3 2 5 5 7 10 12 17 22 29 39 51 68 90119158209277
A(n) mod n ? 0 0 0 2 0 5 0 2 3 7 0 5 0 9 8 10 0 14 0 17

Motivated by a theorem of E. Lucas: If n is prime it divides A(n) exactly, the question whether primality of n follows from n divides A(n) exactly was formulated 1899. So far, they say, nobody has found a composite n that divides A(n). Such a number would be called a Perrin pseudoprime. The article quotes an experiment by Steven Arno of the Supercomputing Research Center in Bowie, Md., where a lower bound of 15 digits for the size of the smallest Perrin pseudoprime was obtained in 1991.

On July 3rd, 1996, I was able to find the two smallest Perrin pseudoprimes:

Somewhat later: Sifting Richard Pinch's table of the 246683 Carmichael numbers up to 10^16, I counted 150 Perrin pseudoprimes.

About the computation

A(n) can be evaluated straightforward, starting with the initial values and keeping the last three results. On a 32 bit computer, A(78)=3354494070 is the last member of the sequence that can be computed without the utilization of an infinite-precision arithmetic package. AI languages such as SICStus or ECLiPSe Prolog provide this convenience transparently. A(271441), a 33150 digit number, can be computed without any changes to the (trivial) evaluation algorithm.
If the objective of the computation is to check for the congruence of the result with 0 modulo n, the intermediate results may of course be reduced modulo n. Replacing the linear evaluation of A(n) mod n by a binary method results in an O(log(n)) algorithm.

You can try it right away. Maybe you are lucky and spot another Perrin pseudoprime.

A(n) mod m calculator (a Prolog program)

Enter an integer n>0:


Enter an integer m>1 (defaults to n if left blank):


(Large numbers may be chopped into several lines, non-numerical material is discarded)

URL of this page: http://www.ai.univie.ac.at/perrin.html

Please direct questions and comments towards:

Christian Holzbaur http://www.ai.univie.ac.at/~christia