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,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

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.

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

Adjacent sequences: A275609 A275610 A275611 * A275613 A275614 A275615

Keyword

nonn

Author

Dana Jacobsen, Aug 03 2016

Status

approved