A081264 Odd Fibonacci pseudoprimes: odd composite numbers k such that either (1) k divides Fibonacci(k-1) if k == +-1 (mod 5) or (2) k divides Fibonacci(k+1) if k == +-2 (mod 5).

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, 11663, 13201, 13981, 15251, 17119, 17711, 18407, 19043, 23407, 25877, 27323, 30889, 34561, 34943, 35207, 39203, 40501, 50183, 51841, 51983, 52701, 53663, 60377, 64079, 64681

Offset

1,1

Comments

Lehmer shows that there are an infinite number of Fibonacci pseudoprimes (FPPs). In particular, the number Fibonacci(2p) is an FPP for all primes p > 5. Anderson lists over 5000 FPPs, while Jacobsen lists over 170000. The sequences A069106 and A069107 give k such that k divides Fibonacci(k-1) and k divides Fibonacci(k+1), respectively. See A141137 for even FPPs.

References

R. Crandall and C. Pomerance, Primes Numbers: A Computational Perspective, Springer, 2002, p. 131.

P. Ribenboim, The New Book of Prime Number Records, Springer, 1995, p. 127.

A. Witno, Theory of Numbers, BookSurge, North Charleston, SC; see p. 83.

Links

P. G. Anderson and Dana Jacobsen, Table of n, a(n) for n = 1..10000 (first 5861 terms from P. G. Anderson)

P. G. Anderson, Fibonacci pseudoprimes under 2,217,967,487 and their factors

Dorin Andrica and Ovidiu Bagdasar, Recurrent Sequences: Key Results, Applications, and Problems, Springer (2020), p. 88.

Dorin Andrica and Ovidiu Bagdasar, On Generalized Lucas Pseudoprimality of Level k, Mathematics (2021) Vol. 9, 838.

Dorin Andrica, Vlad Crişan, and Fawzi Al-Thukair, On Fibonacci and Lucas sequences modulo a prime and primality testing, Arab Journal of Mathematical Sciences, 2017.

Dana Jacobsen, Pseudoprime Statistics, Tables, and Data (includes terms through 7e12)

E. Lehmer, On the infinitude of Fibonacci pseudoprimes, Fibonacci Quarterly, 2, 1964, pp. 229-230.

Andrzej Rotkiewicz, Arithmetic progressions formed by pseudoprimes, Acta Mathematica et Informatica Universitatis Ostraviensis, vol. 8 (2000), issue 1, pp. 61-74.

Eric Weisstein's World of Mathematics, Fibonacci Pseudoprime

Wikipedia, Fibonacci pseudoprime

Index entries for sequences related to pseudoprimes

Maple

filter:= proc(n) local M, r;
   uses LinearAlgebra:-Modular;
   if isprime(n) then return false fi;
   M:= Mod(n, [[1, 1], [1, 0]], float[8]);
   if n^2 mod 5 = 1 then r:= n-1 else r:= n+1 fi;
   M:= MatrixPower(n, M, r);
   M[1, 2] = 0
end proc:select(filter, [2*i+1 $ i=1..10^5]); # Robert Israel, Aug 05 2015

Mathematica

lst={}; f0=0; f1=1; Do[f2=f1+f0; If[n>1&&!PrimeQ[n], If[MemberQ[{1, 4}, Mod[n, 5]], If[Mod[f0, n]==0, AppendTo[lst, n]]]; If[MemberQ[{2, 3}, Mod[n, 5]], If[Mod[f2, n]==0, AppendTo[lst, n]]]]; f0=f1; f1=f2, {n, 100000}]; lst
ocnQ[n_]:=CompositeQ[n]&&Which[Mod[n, 5]==1, Divisible[Fibonacci[ n-1], n], Mod[n, 5] == 4, Divisible[ Fibonacci[n-1], n], Mod[n, 5]==2, Divisible[ Fibonacci[n+1], n], Mod[n, 5]==3, Divisible[Fibonacci[n+1], n], True, False]; Select[Range[1, 65001, 2], ocnQ] (* Harvey P. Dale, Aug 23 2017 *)

Prog

(Perl) use ntheory ":all"; foroddcomposites { $e = (0, -1, 1, 1, -1)[$_%5]; say unless $e==0 || (lucas_sequence($_, 1, -1, $_+$e))[0] } 1e10; # Dana Jacobsen, Aug 05 2015

Crossrefs

Cf. A069106, A069107.

Sequence in context: A340118 A339517 A217120 * A069107 A094412 A182504

Adjacent sequences: A081261 A081262 A081263 * A081265 A081266 A081267

Keyword

nice,nonn

Author

T. D. Noe, Mar 15 2003, Jun 09 2008

Status

approved