A275613 Restricted Perrin pseudoprimes (Grantham 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 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.

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.

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.

Links

Dana Jacobsen, Table of n, a(n) for n = 1..701

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($_, 3); } 1e8; # Dana Jacobsen, Aug 03 2016
(PARI) perrin3(n) = {
  my(M, L, S, j, A, B, C, D);
  if(n==2||n==23, return(1));
  if(n%2==0, return(0));
  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 == 0, return(0));
  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 (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);
}

Crossrefs

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes), A275612 (Adams/Shanks restricted Perrin pseudoprimes).

Sequence in context: A269282 A018187 A275612 * A204805 A216903 A114681

Adjacent sequences: A275610 A275611 A275612 * A275614 A275615 A275616

Keyword

nonn

Author

Dana Jacobsen, Aug 03 2016

Status

approved