login
Unrestricted Perrin pseudoprimes.
16

%I #126 Apr 04 2024 10:55:01

%S 271441,904631,16532714,24658561,27422714,27664033,46672291,102690901,

%T 130944133,196075949,214038533,517697641,545670533,801123451,

%U 855073301,903136901,970355431,1091327579,1133818561,1235188597,1389675541,1502682721,2059739221,2304156469,2976407809,3273820903

%N Unrestricted Perrin pseudoprimes.

%C "The column Mathematical Recreations by Ian Stewart in the June 1996 issue of Scientific American discusses the Perrin sequence [A001608] A(n) defined by A(0)=3, A(1)=0, A(2)=2, A(n+1)=A(n-1)+A(n-2). Motivated by a theorem of E. Lucas: If n is prime it divides A(n) exactly, the question whether primality of n follows from n divides A(n) exactly was formulated 1899. So far, they say, nobody has found a composite n that divides A(n). Such a number would be called a Perrin pseudoprime. The article quotes an experiment by Steven Arno of the Supercomputing Research Center in Bowie, Md., where a lower bound of 15 digits for the size of the smallest Perrin pseudoprime was obtained in 1991. On Jul 3rd, 1996, I was able to find the two smallest Perrin pseudoprimes:" [Holzbaur] - _Robert G. Wilson v_, Nov 30 2001

%C In the "Feedback" section of his column for November 1996, Ian Stewart mentions that _Jeffrey Shallit_ (Waterloo) had written to him saying that he had found the Perrin pseudoprimes 271441 and 904631 in 1982.

%C There are 765 Perrin pseudoprimes which are also Carmichael numbers less than 2^64. - _Dana Jacobsen_, May 10 2015

%C There are 101994 Perrin pseudoprimes which are also Fermat pseudoprimes to base 2 less than 2^64. - _Dana Jacobsen_, May 10 2015

%C Difference in the number of unlabeled maximal independent sets of an a(n)-cycle graph A127687(a(n)) times a(n), from value of Perrin(a(n)) such that Perrin(a(n)) mod a(n) = Sum_{d|a(n)} (Perrin(d)*Phi(a(n)/d)) mod a(n) [d<a(n)]==0 (mod a(n)); Perrin = A001608, Phi = A000010. - _Richard Turk_, Aug 11 2015

%C There are two known Perrin pseudoprimes that are squares: a(1)=271441=521^2 and a(76)=36366108601=190699^2. In A173656 it is claimed that there are no others < (10^9)^2. - _Hugo Pfoertner_, Sep 01 2017

%H Dana Jacobsen, <a href="/A013998/b013998.txt">Table of n, a(n) for n = 1..1702</a> (first 658 terms from Robert Harley)

%H William W. Adams and Daniel 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 Robert Dougherty-Bliss, <a href="https://sites.math.rutgers.edu/~zeilberg/Theses/RobertDoughertyBlissThesis.pdf">Experimental Methods in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 34.

%H Jon Grantham, <a href="https://doi.org/10.1016/j.jnt.2009.11.008">There are infinitely many Perrin pseudoprimes</a>, Journal of Number Theory Volume 130, Issue 5, May 2010, Pages 1117-1128.

%H Christian Holzbaur, <a href="/A013998/a013998.html">Perrin pseudoprimes</a> [Original link broke many years ago. This is a cached copy from the WayBack machine, dated Apr 24 2006]

%H Dana Jacobsen, <a href="http://ntheory.org/pseudoprimes.html">Pseudoprime Statistics, Tables, and Data</a>

%H Holger Stephan, <a href="http://www.wias-berlin.de/people/stephan/ppp1.out">Perrin pseudoprimes up to 10^16 with factorization.</a> [Note: this is not a complete list of Perrin pseudoprimes in the range, _Dana Jacobsen_, May 10 2015]

%H Holger Stephan, <a href="/A013998/a013998.txt">Perrin pseudoprimes up to 10^16 with factorization.</a> [Note: this is not a complete list of Perrin pseudoprimes in the range, _Dana Jacobsen_, May 10 2015] [Cached copy, with permission]

%H Holger Stephan, <a href="https://arxiv.org/abs/2002.03756">Millions of Perrin pseudoprimes including a few giants</a>, arXiv:2002.03756 [math.NA], 2020.

%H Ian Stewart, <a href="http://web.archive.org/web/20120330094207/http://www.fortunecity.com/emachines/e11/86/padovan.html">Tales of a Neglected Number.</a> Mathematical Recreations, Scientific American, 6 (1996), 92-93.

%H Ian Stewart, <a href="https://www.jstor.org/stable/24989576">Tales of a Neglected Number</a>, Mathematical Recreations, Scientific American, Vol. 274, No. 6 (1996), pp. 102-103.

%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 (PARI)

%o N=10^10;

%o default(primelimit,N);

%o M = [0, 1, 0; 0, 0, 1; 1, 1, 0];

%o a(n)=lift( trace( Mod(M,n)^n ) ); /* A215339(n) */

%o { for (n=1,N,

%o if ( isprime(n), next() );

%o if ( a(n)==0, print1(n,", "); );

%o ); }

%o /* _Joerg Arndt_, Aug 16 2012 */

%o (Perl)

%o use ntheory ":all";

%o forcomposites { say if is_perrin_pseudoprime($_) } 1e10;

%o # _Dana Jacobsen_, May 10 2015

%Y Cf. A000010, A001608, A018187, A173656.

%K nonn

%O 1,1

%A _R. K. Guy_

%E More terms from alipson(AT)cix.compulink.co.uk (Andrew Lipson)