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 | 90 | 119 | 158 | 209 | 277 |
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:
- PPP(1): 271441 = 521 * 521
- PPP(2): 904631 = 7 * 13 * 9941
Somewhat later:
- PPP(3): 16532714 = 2 * 11 * 11 * 53 * 1289
- PPP(4): 24658561 = 19 * 271 * 4789
- PPP(5): 27422714 = 2 * 11 * 11 * 47 * 2411
- PPP(6): 27664033 = 3037 * 9109
- PPP(7): 46672291 = 4831 * 9661
- PPP(8): 102690901 = 5851 * 17551
- PPP(9): 130944133 = 6607 * 19819
- PPP(10): 196075949 = 5717 * 34297
- PPP(11): 214038533 = 8447 * 25339
- PPP(12): 517697641 = 6311 * 82031
- PPP(13): 545670533 = 13487 * 40459
- PPP(14): 801123451 = 8951 * 89501
- PPP(15): 855073301 = 16883 * 50647
- PPP(16): 903136901 = 17351 * 52051
- PPP(17): 970355431 = 22027 * 44053
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)
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