A Perrin pseudoprime in the unrestricted sense is a composite number
satisfying , where is an element of the Perrin
sequence 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, ... (OEIS A001608).
Every prime number satisfies . The smallest unrestricted
Perrin pseudoprimes are 271441, 904631, 16532714, 24658561, ... (OEIS A013998).
Unlike a Perrin prime, a Perrin pseudoprime is a
composite index, rather than a prime number value
of the Perrin sequence.
Adams and Shanks (1982) discovered the smallest unrestricted Perrin pseudoprime after unsuccessful searches by Perrin (1899), Malo (1900), Escot (1901), and Jarden (1966). Stewart (1996) incorrectly stated that no Perrin pseudoprimes were then known.
Grantham (2001) defined a Perrin pseudoprime with integer parameters
to be an oddcomposite
number
for which either
where
is the discriminant of and is the Jacobi symbol.
The original Perrin sequence corresponds to and . For these parameters, Grantham's restricted
Perrin pseudoprimes begin 27664033, 46672291, 102690901, ... (OEIS A275613).
The minimal restricted Perrin test imposes only and on a composite
number. Its pseudoprimes begin 27664033, 46672291, 102690901,
... (OEIS A018187) and need not satisfy Grantham's
signature conditions. Kurtz et al. (1986) found all 55 minimal restricted
Perrin pseudoprimes less than , each of which has
an S-recurrence relation signature.
Adams, W. and Shanks, D. "Strong Primality Tests that Are Not Sufficient." Math. Comput.39, 255-300, 1982.Adams,
W. W. "Characterizing Pseudoprimes for Third-Order Linear Recurrence Sequences."
Math. Comput.48, 1-15, 1987.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."
Math. Comput.70, 873-891, 2001. https://doi.org/10.1090/s0025-5718-00-01197-2.Holzbaur,
C. "Perrin Pseudoprimes." http://ftp.ai.univie.ac.at/perrin.html.Jarden,
D. Recurring
Sequences: A Collection of Papers, Including New Factorizations of Fibonacci and
Lucas Numbers. Jerusalem, Israel: 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.Malo, E. "Réponse
à 1484." L'Intermédiare des Math.7, 280-282 and
312-314, 1900.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. Sequences A001608/M0429,
A013998, A018187,
and A275613 in "The On-Line Encyclopedia
of Integer Sequences."Stewart, I. "Tales of a Neglected Number."
Sci. Amer.274, 102-103, June 1996.