login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018187 Restricted Perrin pseudoprimes. 8
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 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
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.
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
KEYWORD
nonn
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)