A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).

27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121, 7279379941, 7825642579

Offset: 1

Author

Dana Jacobsen, Aug 03 2016

Keywords

• nonn

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.

Crossrefs

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes)

Programs

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

Perl

use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($,2); } 1e8; # _Dana Jacobsen, Aug 03 2016