login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018187 Restricted Perrin pseudoprimes. 6
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 3 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 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).

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.

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 CD-ROM

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), 255-300.

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.

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)) == n-1; }

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 12:43 EST 2017. Contains 295001 sequences.