TOPICS
Search

Perrin Pseudoprime


If p is prime, then p|P(p), where P(p) is a member of the Perrin sequence 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, ... (OEIS A001608). A Perrin pseudoprime is a composite number n such that n|P(n). Several "unrestricted" Perrin pseudoprimes are known, the smallest of which are 271441, 904631, 16532714, 24658561, ... (OEIS A013998).

Adams and Shanks (1982) discovered the smallest unrestricted Perrin pseudoprime after unsuccessful searches by Perrin (1899), Malo (1900), Escot (1901), and Jarden (1966). (A 1996 article by Stewart's stating that no Perrin pseudoprimes were then known was incorrect.)

Grantham generalized the definition of Perrin pseudoprime with parameters (r,s) to be an odd composite number n for which either

1. (Delta/n)=1 and n has an S-recurrence relation signature, or

2. (Delta/n)=-1 and n has a Q-recurrence relation signature,

where (a/b) is the Jacobi symbol. All the 55 Perrin pseudoprimes less than 50×10^9 have been computed by Kurtz et al. (1986). All have S-recurrence relation signature, and form the sequence Sloane calls "restricted" Perrin pseudoprimes: 27664033, 46672291, 102690901, ... (OEIS A018187).


See also

Perrin Sequence, Pseudoprime

Explore with Wolfram|Alpha

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: A Collection of Papers, Including New Factorizations of Fibonacci and Lucas Numbers. Jerusalem: Riveon Lematematika, 1966.Kurtz, G. C.; Shanks, D.; and Williams, H. C. "Fast Primality Tests for Numbers Less than 50·10^9." Math. Comput. 46, 691-701, 1986.Malo, E. L'Intermédiare des Math. 7, 281 and 312, 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, and A018187 in "The On-Line Encyclopedia of Integer Sequences."Stewart, I. "Tales of a Neglected Number." Sci. Amer. 274, 102-103, June 1996.

Referenced on Wolfram|Alpha

Perrin Pseudoprime

Cite this as:

Weisstein, Eric W. "Perrin Pseudoprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PerrinPseudoprime.html

Subject classifications