# Perrin pseudoprime

Given the Perrin sequence^{}, ${a}_{0}=3$, ${a}_{1}=0$, ${a}_{2}=2$ and ${a}_{n}={a}_{n-3}+{a}_{n-2}$ for $n>2$, if $n$ is not prime yet $n|{a}_{n}$, that number is then called a Perrin pseudoprime^{}. The first few Perrin pseudoprimes are 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291 (listed in A013998 of Sloane’s OEIS).

By itself this is not a good enough test of primality. Further requiring that ${a}_{n}\equiv 0modn$ and ${a}_{-n}\equiv 1modn$ improves the test but not enough to be preferable to actually factoring out the number. The first few strong Perrin pseudoprimes are 27664033, 46672291, 102690901, 130944133, 517697641 (listed in A018187 of Sloane’s OEIS).

Unlike Perrin pseudoprimes, most other pseudoprimes^{} (http://planetmath.org/PseudoprimeP) are because of a congruence relation^{} to a given base.

Title | Perrin pseudoprime |
---|---|

Canonical name | PerrinPseudoprime |

Date of creation | 2013-03-22 16:11:33 |

Last modified on | 2013-03-22 16:11:33 |

Owner | CompositeFan (12809) |

Last modified by | CompositeFan (12809) |

Numerical id | 5 |

Author | CompositeFan (12809) |

Entry type | Definition |

Classification | msc 11B39 |

Defines | strong Perrin pseudoprime |