TOPICS
Search

Recurrence Relation Signature


Let a sequence be defined by

A_(-1)=s
(1)
A_0=3
(2)
A_1=r
(3)
A_n=rA_(n-1)-sA_(n-2)+A_(n-3).
(4)

Also define the associated polynomial

 f(x)=x^3-rx^2+sx+1,
(5)

and let Delta be its discriminant. The Perrin sequence is a special case corresponding to A_n(0,-1). The signature mod m of an integer n with respect to the sequence A_k(r,s) is then defined as the 6-tuple (A_(-n-1), A_(-n), A_(-n+1), A_(n-1), A_n, A_(n+1)) (mod m).

1. An integer n has an S-signature if its signature (mod n) is (A_(-2), A_(-1), A_0, A_0, A_1, A_2).

2. An integer n has a Q-signature if its signature (mod n) is congruent to (A,s,B,B,r,C) where, for some integer a with f(a)=0 (mod n), A=a^(-2)+2a, B=-ra^2+(r^2-s)a, and C=a^2+2a^(-1).

3. An integer n has an I-signature if its signature (mod n) is congruent to (r,s,D^',D,r,s), where D^'+D=rs-3 and (D^'-D)^2=Delta.


See also

Perrin Pseudoprime

Explore with Wolfram|Alpha

References

Adams, W. and Shanks, D. "Strong Primality Tests that Are Not Sufficient." Math. Comput. 39, 255-300, 1982.Grantham, J. "Frobenius Pseudoprimes." http://www.clark.net/pub/grantham/pseudo/pseudo1.ps.

Referenced on Wolfram|Alpha

Recurrence Relation Signature

Cite this as:

Weisstein, Eric W. "Recurrence Relation Signature." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RecurrenceRelationSignature.html

Subject classifications