A018187 Restricted Perrin pseudoprimes.

27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121

Offset: 1

Author

R. K. Guy

Keywords

• nonn

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

• 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

Crossrefs

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).

Programs

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

Perl

use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($,1); } 1e8; # _Dana Jacobsen, Aug 03 2016