OFFSET
1,1
COMMENTS
These are odd composites which have an acceptable signature mod n for the Perrin sequence (A001608), using the definition given by Arno (1991). Grantham (2000) gives a generalized definition for cubics, with the Perrin sequence being the parameters r=0, s=-1.
This is similar to the Adams and Shanks (1982) test, with three exceptions: (1) pseudoprimes must be odd composites, (2) S-signatures with (-23|n) = 0 are not allowed, and (3) the quadratic form test for I-signatures is removed.
Below 5*10^13, there are no even pseudoprimes to the minimal restricted test (A018187), hence the first difference is not seen. Also below 5*10^13, there are no pseudoprimes with an I-signature congruence, so the third difference is also not seen. There are pseudoprimes divisible by 23 to the Adams/Shanks signature test (A275612), which are not pseudoprimes to this test.
LINKS
Dana Jacobsen, Table of n, a(n) for n = 1..701
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($_, 3); } 1e8; # Dana Jacobsen, Aug 03 2016
(PARI) perrin3(n) = {
my(M, L, S, j, A, B, C, D);
if(n==2||n==23, return(1));
if(n%2==0, return(0));
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 == 0, return(0));
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 (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);
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Dana Jacobsen, Aug 03 2016
STATUS
approved