If is Prime, then , where is a member of the Perrin Sequence 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, ... (Sloane's A001608). A Perrin pseudoprime is a Composite Number such that . Several ``unrestricted'' Perrin pseudoprimes are known, the smallest of which are 271441, 904631, 16532714, 24658561, ... (Sloane's A013998).
Adams and Shanks (1982) discovered the smallest unrestricted Perrin pseudoprime after unsuccessful searches by Perrin (1899), Malo (1900), Escot (1901), and Jarden (1966). (Stewart's 1996 article stating no Perrin pseudoprimes were known was in error.)
Grantham (1996) generalized the definition of Perrin pseudoprime with parameters to be an Odd Composite Number for which either
See also Perrin Sequence, Pseudoprime
References
Adams, W. W. ``Characterizing Pseudoprimes for Third-Order Linear Recurrence Sequences.'' Math Comput. 48, 1-15, 1987.
Adams, W. and Shanks, D. ``Strong Primality Tests that Are Not Sufficient.'' Math. Comput. 39, 255-300, 1982.
Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press,
p. 305, 1996.
Escot, E.-B. ``Solution to Item 1484.'' L'Intermédiare des Math. 8, 63-64, 1901.
Grantham, J. ``Frobenius Pseudoprimes.''
http://www.clark.net/pub/grantham/pseudo/pseudo1.ps
Holzbaur, C. ``Perrin Pseudoprimes.'' http://ftp.ai.univie.ac.at/perrin.html.
Jarden, D. Recurring Sequences. Jerusalem: Riveon Lematematika, 1966.
Kurtz, G. C.; Shanks, D.; and Williams, H. C. ``Fast Primality Tests for Numbers Less than .''
Math. Comput. 46, 691-701, 1986.
Perrin, R. ``Item 1484.'' L'Intermédiare des Math. 6, 76-77, 1899.
Ribenboim, P. The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, p. 135, 1996.
Sloane, N. J. A.
A013998,
A018187, and
A001608/M0429
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html.
Stewart, I. ``Tales of a Neglected Number.'' Sci. Amer. 274, 102-103, June 1996.
© 1996-9 Eric W. Weisstein