A recurrence relation signature is a six-term residue tuple associated with the sequence defined by
|
(1)
| |||
|
(2)
| |||
|
(3)
| |||
|
(4)
|
for integer parameters and
,
with the recurrence relation extended to all
integer indices. The associated polynomial
is
|
(5)
|
where
is its discriminant. The Perrin
sequence is a special case corresponding to
. For a positive
integer
, the signature mod
of an integer
with respect to the sequence
is then defined as the 6-tuple (
,
,
,
,
,
)
(mod
). For a positive integer
, the following signatures are defined, with every congruence taken modulo
(Grantham 2001).
1. The integer has an S-signature if its signature (mod
) is congruent to (
,
,
,
,
,
).
2. The integer has a Q-signature if its signature (mod
) is congruent to (
) where, for some integer
with
,
,
, and
.
3. The integer has an I-signature if its signature (mod
) is congruent to (
), where
and
.