login
A275612
Restricted Perrin pseudoprimes (Adams and Shanks definition)
2
27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121, 7279379941, 7825642579
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
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
Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes)
Sequence in context: A258688 A269282 A018187 * A275613 A204805 A216903
KEYWORD
nonn
AUTHOR
Dana Jacobsen, Aug 03 2016
STATUS
approved