cp's OEIS Frontend

A018187 Restricted Perrin pseudoprimes.

%I A018187 #43 Feb 16 2025 08:32:33
%S A018187 27664033,46672291,102690901,130944133,517697641,545670533,801123451,
%T A018187 855073301,970355431,1235188597,3273820903,3841324339,3924969689,
%U A018187 4982970241,5130186571,5242624003,6335800411,7045248121
%N A018187 Restricted Perrin pseudoprimes.
%C A018187 From _Dana Jacobsen_, Aug 03 2016: (Start)
%C A018187 These are the "minimal restricted" Perrin pseudoprimes.  They meet conditions (4) and (5) from Adams and Shanks (1982), equivalent to condition (7) from Kurtz et al. (1986).  That is, A(n) = 0 mod p and A(-n) = -1 mod p.  Kurtz et al. call this the "minimal test", Wagon (1999) calls this the "strong Perrin test".
%C A018187 Further restrictions (Adams and Shanks, Arno / Grantham) lead to subsets of this sequence.
%C A018187 Kurtz et al. (1986) state that all acceptables (numbers where A(n) = 0 mod p and A(-n) = -1 mod p) <= 50*10^9 have S-type signatures.  The first example where this does not hold is 16043638781521, which does not have an S-signature (nor an I- or Q-type signature).
%C A018187 The first example of a pseudoprime in this sequence that does not pass the Adams/Shanks signature test is 167385219121, with an S-signature but the wrong Jacobi symbol.
%C A018187 Some sources have conjectured the restricted Perrin pseudoprimes can be derived from the unrestricted Perrin pseudoprimes by checking if { M=[0,1,0; 0,0,1; 1,1,0]; Mod(M,n) == Mod(M,n)^n }. Counterexamples include 52437986833, 60518537641, 364573433665, and 4094040693601. (End)
%D A018187 S. Wagon, Mathematica in action, 2nd ed., 1999, pp. 402 - 403 and Mathematica notebook for Chapter 18 in attached CD-ROM
%H A018187 Dana Jacobsen, <a href="/A018187/b018187.txt">Table of n, a(n) for n = 1..712</a>
%H A018187 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 A018187 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 A018187 Dana Jacobsen, <a href="http://ntheory.org/primality/perrin.html">Perrin Primality Tests</a>.
%H A018187 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.
%H A018187 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerrinPseudoprime.html">Perrin Pseudoprime.</a>
%H A018187 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%o A018187 (Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_,1); } 1e8; # _Dana Jacobsen_, Aug 03 2016
%o A018187 (PARI) is(n) = { lift(trace(Mod([0,1,0; 0,0,1; 1,1,0],n)^n)) == 0 && lift(trace(Mod([0,1,0; 0,0,1; 1,0,-1],n)^n)) == n-1; }
%o A018187 forcomposite(n=1,1e8,is(n)&&print(n)) \\ _Dana Jacobsen_, Aug 03 2016
%Y A018187 Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).
%K A018187 nonn
%O A018187 1,1
%A A018187 _R. K. Guy_