cp's OEIS Frontend

A275613 Restricted Perrin pseudoprimes (Grantham definition).

%I A275613 #19 Jul 27 2024 02:53:56
%S A275613 27664033,46672291,102690901,130944133,517697641,545670533,801123451,
%T A275613 855073301,970355431,1235188597,3273820903,3841324339,3924969689,
%U A275613 4982970241,5130186571,5242624003,6335800411,7045248121,7279379941,7825642579
%N A275613 Restricted Perrin pseudoprimes (Grantham definition).
%C A275613 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.
%C A275613 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.
%C A275613 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.
%H A275613 Dana Jacobsen, <a href="/A275613/b275613.txt">Table of n, a(n) for n = 1..701</a>
%H A275613 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 A275613 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 A275613 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 A275613 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 A275613 Dana Jacobsen, <a href="http://ntheory.org/primality/perrin.html">Perrin Primality Tests</a>.
%H A275613 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 A275613 (Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_,3); } 1e8; # _Dana Jacobsen_, Aug 03 2016
%o A275613 (PARI) perrin3(n) = {
%o A275613   my(M,L,S,j,A,B,C,D);
%o A275613   if(n==2||n==23,return(1));
%o A275613   if(n%2==0,return(0));
%o A275613   M=Mod( [0,1,0; 0,0,1; 1,1,0], n)^n;
%o A275613   L=Mod( [0,1,0; 0,0,1; 1,0,-1], n)^n;
%o A275613   S=[ 3*L[3,2]-L[3,3],   3*L[2,2]-L[2,3],   3*L[1,2]-L[1,3], \
%o A275613       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 A275613   if (S[5] != 0 || S[2] != n-1,return(0));
%o A275613   j = kronecker(-23,n);
%o A275613   if (j == 0,return(0));
%o A275613   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 A275613   if (S[1] == 1 && S[3] == 3 && S[4] == 3 && S[6] == 2, return(1));
%o A275613   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));
%o A275613   return(0);
%o A275613 }
%Y A275613 Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes), A275612 (Adams/Shanks restricted Perrin pseudoprimes).
%K A275613 nonn
%O A275613 1,1
%A A275613 _Dana Jacobsen_, Aug 03 2016