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