|
%I #42 Sep 24 2023 10:42:53
%S 27664033,46672291,102690901,130944133,517697641,545670533,801123451,
%T 855073301,970355431,1235188597,3273820903,3841324339,3924969689,
%U 4982970241,5130186571,5242624003,6335800411,7045248121
%N Restricted Perrin pseudoprimes.
%C From _Dana Jacobsen_, Aug 03 2016: (Start)
%C 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".
%C Further restrictions (Adams and Shanks, Arno / Grantham) lead to subsets of this sequence.
%C 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).
%C 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.
%C 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)
%D S. Wagon, Mathematica in action, 2nd ed., 1999, pp. 402 - 403 and Mathematica notebook for Chapter 18 in attached CD-ROM
%H Dana Jacobsen, <a href="/A018187/b018187.txt">Table of n, a(n) for n = 1..712</a>
%H W. W. Adams and D. Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1982-0658231-9">Strong primality tests that are not sufficient</a>, Math. Comp. 39 (1982), 255-300.
%H Jon Grantham, <a href="http://dx.doi.org/10.1016/j.jnt.2009.11.008">There are infinitely many Perrin pseudoprimes</a>, J. Number Theory 130 (2010) 1117-1128.
%H Dana Jacobsen, <a href="http://ntheory.org/primality/perrin.html">Perrin Primality Tests</a>.
%H G. C. Kurtz, Daniel Shanks and H. C. Williams, <a href="http://dx.doi.org/10.1090/S0025-5718-1986-0829639-7">Fast Primality Tests for Numbers < 50*10^9</a>, Math. Comp., 46 (1986), 691-701.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerrinPseudoprime.html">Perrin Pseudoprime.</a>
%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%o (Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_,1); } 1e8; # _Dana Jacobsen_, Aug 03 2016
%o (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; }
%o forcomposite(n=1,1e8,is(n)&&print(n)) \\ _Dana Jacobsen_, Aug 03 2016
%Y Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).
%K nonn
%O 1,1
%A _R. K. Guy_
|
