OFFSET
1,1
COMMENTS
These are composites which have an acceptable signature mod n for the Perrin sequence (A001608). See Adams and Shanks (1982), page 261.
They add additional conditions to the unrestricted Perrin test (A013998) and the minimal restricted test (A018187).
The quadratic form restriction for the I-signature (equation 29 in Adams and Shanks (1982)) is sometimes removed. No pseudoprimes are currently known that match the I-signature congruences. Adams and Shanks note that objections could be raised to its inclusion in the test, and Arno (1991) and Grantham (2000) both drop it.
Kurtz et al. (1986) call these "acceptable composites for the Perrin sequence". - N. J. A. Sloane, Jul 28 2019
LINKS
Dana Jacobsen, Table of n, a(n) for n = 1..706
W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), 371-376.
Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), 873-891.
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 1117-1128.
Dana Jacobsen, Perrin Primality Tests.
G. C. Kurtz, Daniel Shanks and H. C. Williams, Fast Primality Tests for Numbers < 50*10^9, Math. Comp., 46 (1986), 691-701.
PROG
(Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_, 2); } 1e8; # Dana Jacobsen, Aug 03 2016
(PARI) perrin2(n) = {
my(M, L, S, j, A, B, C, D);
M=Mod( [0, 1, 0; 0, 0, 1; 1, 1, 0], n)^n;
L=Mod( [0, 1, 0; 0, 0, 1; 1, 0, -1], n)^n;
S=[ 3*L[3, 2]-L[3, 3], 3*L[2, 2]-L[2, 3], 3*L[1, 2]-L[1, 3], \
3*M[3, 1]+2*M[3, 3], 3*M[1, 1]+2*M[1, 3], 3*M[2, 1]+2*M[2, 3] ];
if (S[5] != 0 || S[2] != n-1, return(0));
j = kronecker(-23, n);
if (j == -1, B=S[3]; A=1+3*B-B^2; C=3*B^2-2; if(S[1]==A && S[3]==B && S[4]==B && S[6] == C && B != 3 && B^3-B==1, return(1), return(0)));
if (S[1] == 1 && S[3] == 3 && S[4] == 3 && S[6] == 2, return(1));
if (j == 1 && S[1] == 0 && S[6] == n-1 && S[3] != S[4] && S[3]+S[4] == n-3 && (S[3]-S[4])^2 == Mod(-23, n), return(1));
return(0);
} \\ Dana Jacobsen, Aug 03 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Dana Jacobsen, Aug 03 2016
STATUS
approved