cp's OEIS Frontend

A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).

%I A275612 #13 Jun 02 2025 12:19:25
%S A275612 27664033,46672291,102690901,130944133,517697641,545670533,801123451,
%T A275612 855073301,970355431,1235188597,3273820903,3841324339,3924969689,
%U A275612 4982970241,5130186571,5242624003,6335800411,7045248121,7279379941,7825642579
%N A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).
%C A275612 These are composites which have an acceptable signature mod n for the Perrin sequence (A001608).  See Adams and Shanks (1982), page 261.
%C A275612 They add additional conditions to the unrestricted Perrin test (A013998) and the minimal restricted test (A018187).
%C A275612 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.
%C A275612 Kurtz et al. (1986) call these "acceptable composites for the Perrin sequence". - _N. J. A. Sloane_, Jul 28 2019
%H A275612 Dana Jacobsen, <a href="/A275612/b275612.txt">Table of n, a(n) for n = 1..706</a>
%H A275612 W. W. Adams and D. Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1982-0658231-9">Strong primality tests that are not sufficient</a>, Math. Comp. 39 (1982), 255-300.
%H A275612 Steven Arno, <a href="http://dx.doi.org/10.1090/S0025-5718-1991-1052083-9">A note on Perrin pseudoprimes</a>, Math. Comp. 56 (1991), 371-376.
%H A275612 Jon Grantham, <a href="http://dx.doi.org/10.1090/S0025-5718-00-01197-2">Frobenius pseudoprimes</a>, Math. Comp. 70 (2001), 873-891.
%H A275612 Jon Grantham, <a href="http://dx.doi.org/10.1016/j.jnt.2009.11.008">There are infinitely many Perrin pseudoprimes</a>, J. Number Theory 130 (2010) 1117-1128.
%H A275612 Dana Jacobsen, <a href="http://ntheory.org/primality/perrin.html">Perrin Primality Tests</a>.
%H A275612 G. C. Kurtz, Daniel Shanks and H. C. Williams, <a href="http://dx.doi.org/10.1090/S0025-5718-1986-0829639-7">Fast Primality Tests for Numbers < 50*10^9</a>, Math. Comp., 46 (1986), 691-701.
%o A275612 (Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_,2); } 1e8; # _Dana Jacobsen_, Aug 03 2016
%o A275612 (PARI) perrin2(n) = {
%o A275612   my(M,L,S,j,A,B,C,D);
%o A275612   M=Mod( [0,1,0; 0,0,1; 1,1,0], n)^n;
%o A275612   L=Mod( [0,1,0; 0,0,1; 1,0,-1], n)^n;
%o A275612   S=[ 3*L[3,2]-L[3,3],   3*L[2,2]-L[2,3],   3*L[1,2]-L[1,3], \
%o A275612       3*M[3,1]+2*M[3,3], 3*M[1,1]+2*M[1,3], 3*M[2,1]+2*M[2,3] ];
%o A275612   if (S[5] != 0 || S[2] != n-1,return(0));
%o A275612   j = kronecker(-23,n);
%o A275612   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)));
%o A275612   if (S[1] == 1 && S[3] == 3 && S[4] == 3 && S[6] == 2, return(1));
%o A275612   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));
%o A275612   return(0);
%o A275612 } \\ _Dana Jacobsen_, Aug 03 2016
%Y A275612 Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes)
%K A275612 nonn
%O A275612 1,1
%A A275612 _Dana Jacobsen_, Aug 03 2016