

A018187


Restricted Perrin pseudoprimes.


7



27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

From Dana Jacobsen, Aug 03 2016: (Start)
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".
Further restrictions (Adams and Shanks, Arno / Grantham) lead to subsets of this sequence.
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 Stype signatures. The first example where this does not hold is 16043638781521, which does not have an Ssignature (nor an I or Qtype signature).
The first example of a pseudoprime in this sequence that does not pass the Adams/Shanks signature test is 167385219121, with an Ssignature but the wrong Jacobi symbol.
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)


REFERENCES

S. Wagon, Mathematica in action, 2nd ed., 1999, pp. 402  403 and Mathematica notebook for Chapter 18 in attached CDROM


LINKS

Dana Jacobsen, Table of n, a(n) for n = 1..712
W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255300.
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 11171128.
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), 691701.
Eric Weisstein's World of Mathematics, Perrin Pseudoprime.
Index entries for sequences related to pseudoprimes


PROG

(Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_, 1); } 1e8; # Dana Jacobsen, Aug 03 2016
(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)) == n1; }
forcomposite(n=1, 1e8, is(n)&&print(n)) \\ Dana Jacobsen, Aug 03 2016


CROSSREFS

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).
Sequence in context: A274367 A258688 A269282 * A275612 A275613 A204805
Adjacent sequences: A018184 A018185 A018186 * A018188 A018189 A018190


KEYWORD

nonn


AUTHOR

R. K. Guy


STATUS

approved



