|
%I #45 Jan 08 2021 18:19:50
%S 4181,5777,6721,10877,13201,15251,34561,51841,64079,64681,67861,68251,
%T 75077,90061,96049,97921,100127,113573,118441,146611,161027,162133,
%U 163081,186961,197209,219781,231703,252601,254321,257761,268801,272611
%N Frobenius pseudoprimes with respect to Fibonacci polynomial x^2 - x - 1.
%C Grantham incorrectly claims that "the first Frobenius pseudoprime with respect to the Fibonacci polynomial x^2 - x - 1 is 5777". Crandall and Pomerance state that the first such Frobenius pseudoprime is actually 4181.
%C The Frobenius (1,-1) pseudoprimes are a subset of the odd Fibonacci pseudoprimes A081264. Among other ways, this can be seen by Theorem 3.6.6 of Crandall and Pomerance (2005) where the Frobenius criterion with respect to x^2 - Px + Q is an additional condition on an input which has passed the Lucas test for the same polynomial. - _Dana Jacobsen_, Aug 05 2015
%C Many other quadratics have a sparser set of pseudoprimes. For example, while there are 98702 pseudoprimes below 10^13 with respect to the Fibonacci polynomial, there are only 3897 for x^2 - 3x - 5. - _Dana Jacobsen_, Aug 05 2015
%C This is the intersection of A049062 and (A081264 union A141137), that is, composite k coprime to 5 such that Fibonacci(k) == (k/5) (mod k) and that k divides Fibonacci(k-(k/5)), where (k/5) is the Legendre or Jacobi symbol. - _Jianing Song_, Sep 12 2018
%D R. Crandall, C. B. Pomerance. Prime Numbers: A Computational Perspective. Springer, 2nd ed., 2005.
%H Amiram Eldar, <a href="/A212424/b212424.txt">Table of n, a(n) for n = 1..10000</a> (from Dana Jacobsen's site, terms 1..653 from Max Alekseyev)
%H Dorin Andrica and Ovidiu Bagdasar, <a href="https://doi.org/10.1007/978-3-030-51502-7">Recurrent Sequences: Key Results, Applications, and Problems</a>, Springer (2020), p. 89.
%H Jon Grantham, <a href="http://dx.doi.org/10.1090/S0025-5718-00-01197-2">Frobenius pseudoprimes</a>, Mathematics of Computation 70 (234): 873-891, 2001. doi: 10.1090/S0025-5718-00-01197-2.
%H Dana Jacobsen, <a href="http://ntheory.org/pseudoprimes.html">Pseudoprime Statistics, Tables, and Data</a> (includes terms through 10^13)
%H A. Rotkiewicz, <a href="http://www.sbc.org.pl/Content/33711/2003_03.pdf">Lucas and Frobenius Pseudoprimes</a>, Annales Mathematicae Silesiane, 17 (2003): 17-39.
%H Lawrence Somer, <a href="http://www.fq.math.ca/Papers1/44-1/quartlawsomer01_2006.pdf">Lucas sequences {Uk} for which U2p and Up are pseudoprimes for almost all primes p</a>, Fibonacci Quart. 44 (2006), no. 1, 7-12.
%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/FrobeniusPseudoprime.html">Frobenius Pseudoprime</a>, MathWorld.
%o (PARI) { isFP(n) = if(ispseudoprime(n),return(0)); t=Mod(x*Mod(1,n),(x^2-x-1)*Mod(1,n))^n; (kronecker(5,n)==-1 && t==1-x)||(kronecker(5,n)==1 && t==x) }
%o (Perl) use ntheory ":all"; foroddcomposites { say if is_frobenius_pseudoprime($_,1,-1) } 1e10; # _Dana Jacobsen_, Aug 05 2015
%Y Cf. A049062, A081264, A141137.
%Y Cf. also A005845, A094063, A094395, A094411.
%Y Terms congruent to 2 or 3 mod 5 are given in A212423.
%K nonn
%O 1,1
%A _Max Alekseyev_, May 16 2012
|
