A069107 -id:A069107 - 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).

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

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

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.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, 2002, p. 131.
Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1995, p. 127.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 104.
A. Witno, Theory of Numbers, BookSurge, North Charleston, SC; see p. 83.

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

Cf. A069106, A069107, A141137.

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

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

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

A123976 Numbers k such that Fibonacci(k-1) is divisible by k.

Original entry on oeis.org

1, 11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251, 269, 271, 281, 311, 331, 349, 359, 379, 389, 401, 409, 419, 421, 431, 439, 442, 449, 461, 479, 491, 499, 509, 521, 541, 569, 571, 599, 601

Offset: 1

Tanya Khovanova, Oct 30 2006

nonn

a(n) is a union of {1}, A069106(n) and A045468(n). Composite a(n) are listed in A069106(n) = {442, 1891, 2737, 4181, 6601, 6721, 8149, ...}. Prime a(n) are listed in A045468(n) = {11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, ...} Primes congruent to {1, 4} mod 5. - Alexander Adamchuk, Nov 02 2006

			Fibonacci(10) = 55, is divisible by 11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A069106, A045468, A069104, A069107, A003631, A000045, A023172, A159051.

import Data.List (elemIndices)
a123976 n = a123976_list !! (n-1)
a123976_list = map (+ 1) $ elemIndices 0 $ zipWith mod a000045_list [1..]
-- Reinhard Zumkeller, Oct 13 2011

Select[Range[1000], IntegerQ[Fibonacci[ # - 1]/# ] &]

is(n)=((Mod([1,1;1,0],n))^n)[2,2]==0 \\ Charles R Greathouse IV, Feb 03 2014

A069104 Numbers m such that m divides Fibonacci(m+1).

Original entry on oeis.org

1, 2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 197, 223, 227, 233, 257, 263, 277, 283, 293, 307, 313, 317, 323, 337, 347, 353, 367, 373, 377, 383, 397, 433, 443, 457, 463, 467, 487, 503, 523, 547, 557

Offset: 1

Benoit Cloitre, Apr 06 2002

Equals A003631 union A069107.

Let u(1)=u(2)=1 and (m+2)*u(m+2) = (m+1)*u(m+1) + m*u(m); then sequence gives values of k such that u(k) is an integer.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A000045, A023172, A123976, A159051.

import Data.List (elemIndices)
a069104 n = a069104_list !! (n-1)
a069104_list =
   map (+ 1) $ elemIndices 0 $ zipWith mod (drop 2 a000045_list) [1..]
-- Reinhard Zumkeller, Oct 13 2011

Select[Range[6! ],IntegerQ[Fibonacci[ #+1]/# ]&] (* Vladimir Joseph Stephan Orlovsky, Apr 03 2009 *)
Select[Range[600],Mod[Fibonacci[#+1],#]==0&] (* Harvey P. Dale, Feb 24 2025 *)

is(n)=((Mod([1,1;1,0],n))^n)[1,1]==0 \\ Charles R Greathouse IV, Feb 03 2014

A094400 Odd n dividing Fibonacci(n)-1 but neither Fibonacci(n-1) nor Fibonacci(n+1).

Original entry on oeis.org

7743, 27071, 54839, 72831, 217257, 388367, 417601, 575599, 670879, 691447, 701569, 809999, 850541, 881011, 1274897, 1365407, 1383249, 1464449, 1504097, 1653751, 1922817, 2106017, 2276351, 2385811, 2474047, 2556553, 2628879, 2697899, 2804543, 3017729, 3352049

Offset: 1

Eric Rowland, May 01 2004

nonn

Giovanni Resta, Table of n, a(n) for n = 1..559 (terms < 4*10^9)

Cf. A069106, A069107, A094394, A094401, A094402.

Select[Range[50000], OddQ[ # ] && Mod[Fibonacci[ # ] - 1, # ] == 0 && ! Mod[Fibonacci[ # - 1], # ] == 0 && ! Mod[Fibonacci[ # + 1], # ] == 0 &]

Offset corrected by and a(15)-a(31) from Giovanni Resta, Jul 20 2013

A094411 Composite numbers k that divide both Fibonacci(k+1) and Fibonacci(k) + 1.

Original entry on oeis.org

5777, 10877, 75077, 80189, 100127, 113573, 161027, 162133, 231703, 430127, 618449, 635627, 667589, 851927, 1033997, 1106327, 1256293, 1388903, 1697183, 2263127, 2435423, 2512889, 2662277, 3175883, 3399527, 3452147, 3774377

Offset: 1

Eric Rowland, May 01 2004

Also composites k that divide both Fibonacci(k+1) and Lucas(k) - 1. - Gary Detlefs, Feb 28 2013

Giovanni Resta, Table of n, a(n) for n = 1..548 (terms < 4*10^9)

Cf. A000032, A000045, A002808, A069107, A094395, A094401, A094412.

Select[Range[2, 50000], ! PrimeQ[ # ] && Mod[Fibonacci[ # + 1], # ] == 0 && Mod[Fibonacci[ # ] + 1, # ] == 0 &]

More terms from Gareth McCaughan, Jun 11 2004
More terms from Ryan Propper, Aug 04 2005
Offset corrected by Giovanni Resta, Jul 20 2013

A094402 Numbers k that divide both Fibonacci(k+1) and Lucas(k) + 1.

Original entry on oeis.org

1, 2, 323, 6479, 11663, 18407, 19043, 23407, 34943, 35207, 39203, 44099, 47519, 51983, 53663, 65471, 78089, 79547, 82983, 86063, 94667, 104663, 109871, 121103, 139359, 142883, 157079, 168299, 195227, 196559, 200147, 233519

Offset: 1

Eric Rowland, May 01 2004

nonn

Giovanni Resta, Table of n, a(n) for n = 1..1000

Cf. A069107, A094398, A094400.

Select[Range[10^5],Divisible[Fibonacci[#+1],#]&&Divisible[LucasL[#]+1,#]&] (* Giorgos Kalogeropoulos, Aug 20 2021 *)

is(n)=(Mod([0,1;1,1],n)^(n+1)*[0;1])[1,1]==0 && (Mod([0,1;1,1],n)^n*[2;1])[1,1]==-1 \\ Charles R Greathouse IV, Nov 04 2016

More terms from Emeric Deutsch, Apr 13 2005

A094412 Numbers k that divide Fibonacci(k+1) but do not divide Fibonacci(k) + 1.

Original entry on oeis.org

323, 377, 2834, 3827, 6479, 11663, 18407, 19043, 20999, 23407, 25877, 27323, 34943, 35207, 39203, 44099, 47519, 50183, 51983, 53663, 60377, 65471, 78089, 79547, 81719, 82983, 84279, 84419, 86063, 90287, 94667, 104663, 109871, 121103, 121393

Offset: 1

Eric Rowland, May 01 2004

nonn

Giovanni Resta, Table of n, a(n) for n = 1..1000

Cf. A000045, A069107, A094395, A094401, A094411.

Select[Range[50000], ! Mod[Fibonacci[ # ] + 1, # ] == 0 && Mod[Fibonacci[ # + 1], # ] == 0 &]
Select[Range[122000],Divisible[{Fibonacci[#+1],Fibonacci[#]+1},#]=={True,False}&] (* Harvey P. Dale, Apr 16 2019 *)

fibmod(n,m)=(Mod([0,1;1,1],m)^n*[0;1])[1,1]
is(n)=fibmod(n+1,n)==0 && fibmod(n,n)!=-1 \\ Charles R Greathouse IV, Nov 04 2016

A100993 Indices k of Fibonacci numbers F(k) (A000045) that are divisible by k-1.

Original entry on oeis.org

2, 3, 4, 8, 14, 18, 24, 38, 44, 48, 54, 68, 74, 84, 98, 104, 108, 114, 128, 138, 158, 164, 168, 174, 194, 198, 224, 228, 234, 258, 264, 278, 284, 294, 308, 314, 318, 324, 338, 348, 354, 368, 374, 378, 384, 398, 434, 444, 458, 464, 468, 488, 504, 524, 548, 558

Offset: 1

Ron Knott, Nov 25 2004

nonn

When k-1 is prime, it is in A003631; when k-1 is composite (such as 323), it is in A069107. - T. D. Noe, Dec 13 2004

			14 is a term because F(14) = 377 = 13*29 is divisible by 13, one less than its index number 14.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Ron Knott, Mathematical Magic of the Fibonacci Numbers.

Cf. A000045, A100992, A003631, A023162, A023173, A069104, A069107.

Select[Range[2, 500], Mod[ Fibonacci[ # ], # - 1] == 0 &] (* Robert G. Wilson v, Nov 26 2004 *)

a(n) = A069104(n) + 1. - T. D. Noe, Dec 13 2004

A128288 a(n) = A023163(n)/3 for n > 1.

Original entry on oeis.org

3, 13, 37, 43, 53, 67, 83, 107, 157, 163, 173, 197, 227, 277, 283, 293, 307, 317, 347, 373, 397, 443, 467, 523, 547, 557, 563, 587, 613, 643, 653, 677, 683, 733, 757, 773, 787, 797, 827, 853, 877, 883, 907, 947, 997, 1013, 1093, 1117, 1123, 1163, 1187, 1213

Offset: 2

Alexander Adamchuk, Feb 24 2007

nonn

3 divides A023163(n) for n > 1. A023163(n) are the numbers n such that Fibonacci(n) == -2 (mod n). Almost all terms of {a(n)} are prime that belong to A003631 = {2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97} (primes congruent to {2, 3} mod 5) that are also the primes p that divide Fibonacci(p+1). The first composite term is a(74) = 1853 = 17*109. The second composite term is 9701 = 89*109. The third composite term is 10877 = 73*149 belong to A069107(n) Composite n such that n divides F(n+1) where F(k) are the Fibonacci numbers. Composite terms in {a(n)} are listed in A128289 = {1853, 9701, 10877, 17261, ...}.

			A023163 begins {1, 9, 39, 111, 129, 159, 201, 249, 321, 471, 489, 519, ...}.
Thus a(2) = A023163(2)/3 = 9/3 = 3, a(3) = A023163(3)/3 = 39/3 = 13.

Cf. A002708, A023172, A023173, A023162, A023163 (numbers k such that Fibonacci(k) == -2 (mod k)).

Cf. A003631, A069107, A128289 (composite terms in A128288).

a(n) = A023163(n)/3 for n > 1.

A128289 Composite terms in A128288(n) = A023163(n)/3 for n>1.

Original entry on oeis.org

1853, 9701, 10877, 17261, 23323, 27403, 75077, 80189, 113573, 120581, 161027, 162133, 163059, 196877, 213749, 291941, 361397, 400987, 427549, 482677, 635627, 667589, 941291, 1030373, 1033997, 1140701, 1196061, 1256293, 1751747, 1816363, 1842581, 2288453, 2662277

Offset: 1

Alexander Adamchuk, Feb 24 2007

nonn

3 divides A023163(n) for n>1. A023163(n) are the numbers n such that Fibonacci(n) == -2 (mod n).
Almost all terms of A128288 are prime that belong to A003631 = {2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97} Primes congruent to {2, 3} mod 5; that are also the primes p that divide Fibonacci(p+1).
a(3) = 10877 = 73*149 belongs to A069107 Composite n such that n divides Fibonacci(n+1).
a(3) = 10877 and a(4) = 17261 belong to A094395 Odd composite n such that n divides Fibonacci(n) + 1.

			a(1) = A128288(74) = 1853 = 17*109.
a(2) = 9701 = 89*109.
a(3) = 10877 = 73*149.
a(4) = 17261 = 41*421.
a(5) = 23323 = 83*281.

Giovanni Resta, Table of n, a(n) for n = 1..1000

Cf. A128288, A002708, A023172, A023173, A023162, A023163 = numbers n such that Fib(n) == -2 (mod n). Cf. A003631, A069107, A094413, A094395 = Odd composite n such that n divides Fibonacci(n) + 1.

Do[ f = Mod[ Fibonacci[3n], 3n ]; If[ !PrimeQ[n] && f == 3n-2, Print[ {n, FactorInteger[n]} ]], {n,1,25000} ]

Two more terms from R. J. Mathar, Oct 08 2007

a(9)-a(33) from Amiram Eldar, Apr 07 2019

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Perl

A123976 Numbers k such that Fibonacci(k-1) is divisible by k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A069104 Numbers m such that m divides Fibonacci(m+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A094400 Odd n dividing Fibonacci(n)-1 but neither Fibonacci(n-1) nor Fibonacci(n+1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A094411 Composite numbers k that divide both Fibonacci(k+1) and Fibonacci(k) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A094402 Numbers k that divide both Fibonacci(k+1) and Lucas(k) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A094412 Numbers k that divide Fibonacci(k+1) but do not divide Fibonacci(k) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A100993 Indices k of Fibonacci numbers F(k) (A000045) that are divisible by k-1.

Views

Author

Keywords

Comments

Examples