cp's OEIS Frontend

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

%I A081264 #70 May 07 2025 14:56:20
%S A081264 323,377,1891,3827,4181,5777,6601,6721,8149,10877,11663,13201,13981,
%T A081264 15251,17119,17711,18407,19043,23407,25877,27323,30889,34561,34943,
%U A081264 35207,39203,40501,50183,51841,51983,52701,53663,60377,64079,64681
%N 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).
%C A081264 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.
%D A081264 R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, 2002, p. 131.
%D A081264 Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1995, p. 127.
%D A081264 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 104.
%D A081264 A. Witno, Theory of Numbers, BookSurge, North Charleston, SC; see p. 83.
%H A081264 P. G. Anderson and Dana Jacobsen, <a href="/A081264/b081264.txt">Table of n, a(n) for n = 1..10000</a> (first 5861 terms from P. G. Anderson)
%H A081264 P. G. Anderson, <a href="http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp">Fibonacci pseudoprimes under 2,217,967,487 and their factors</a>
%H A081264 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. 88.
%H A081264 Dorin Andrica and Ovidiu Bagdasar, <a href="https://doi.org/10.3390/math9080838">On Generalized Lucas Pseudoprimality of Level k</a>, Mathematics (2021) Vol. 9, 838.
%H A081264 Dorin Andrica, Vlad Crişan, and Fawzi Al-Thukair, <a href="https://dx.doi.org/10.1016/j.ajmsc.2017.06.002">On Fibonacci and Lucas sequences modulo a prime and primality testing</a>, Arab Journal of Mathematical Sciences, 2017.
%H A081264 Dana Jacobsen, <a href="http://ntheory.org/pseudoprimes.html">Pseudoprime Statistics, Tables, and Data</a> (includes terms through 7e12)
%H A081264 E. Lehmer, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/2-3/lehmer.pdf">On the infinitude of Fibonacci pseudoprimes</a>, Fibonacci Quarterly, 2, 1964, pp. 229-230.
%H A081264 Andrzej Rotkiewicz, <a href="http://hdl.handle.net/10338.dmlcz/120560">Arithmetic progressions formed by pseudoprimes</a>, Acta Mathematica et Informatica Universitatis Ostraviensis, vol. 8 (2000), issue 1, pp. 61-74.
%H A081264 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FibonacciPseudoprime.html">Fibonacci Pseudoprime</a>
%H A081264 Wikipedia, <a href="http://en.wikipedia.org/wiki/Fibonacci_pseudoprime">Fibonacci pseudoprime</a>
%H A081264 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%p A081264 filter:= proc(n) local M,r;
%p A081264    uses LinearAlgebra:-Modular;
%p A081264    if isprime(n) then return false fi;
%p A081264    M:= Mod(n, [[1,1],[1,0]],float[8]);
%p A081264    if n^2 mod 5 = 1 then r:= n-1 else r:= n+1 fi;
%p A081264    M:= MatrixPower(n,M,r);
%p A081264    M[1,2] = 0
%p A081264 end proc:select(filter, [2*i+1 $ i=1..10^5]); # _Robert Israel_, Aug 05 2015
%t A081264 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
%t A081264 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 *)
%o A081264 (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
%Y A081264 Cf. A069106, A069107, A141137.
%K A081264 nice,nonn
%O A081264 1,1
%A A081264 _T. D. Noe_, Mar 15 2003, Jun 09 2008