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

 

Logo


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 March 26 20:41 EDT 2017. Contains 284137 sequences.