PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (231)
Orphanage
Unclass'd
Unproven (514)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
[parent] Perrin pseudoprime (Definition)

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\vert 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 0 \mod n$ and $ a_{-n} \equiv 1 \mod n$ 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 are pseudoprimes because of a congruence relation to a given base.



"Perrin pseudoprime" is owned by CompositeFan.
(view preamble | get metadata)

View style:

Also defines:  strong Perrin pseudoprime

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: base, congruence relation, primality, OEIS, number, prime, Perrin sequence
There is 1 reference to this entry.

This is version 2 of Perrin pseudoprime, born on 2006-08-23, modified 2007-03-27.
Object id is 8284, canonical name is PerrinPseudoprime.
Accessed 1067 times total.

Classification:
AMS MSC: 11B39 (Number theory :: Sequences and sets :: Fibonacci and Lucas numbers and polynomials and generalizations)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)