A069106 -id:A069106 - 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

A106535 Numbers k such that the smallest x > 1 for which Fibonacci(x) == 0 mod k is x = k - 1.

Original entry on oeis.org

11, 19, 31, 59, 71, 79, 131, 179, 191, 239, 251, 271, 311, 359, 379, 419, 431, 439, 479, 491, 499, 571, 599, 631, 659, 719, 739, 751, 839, 971, 1019, 1039, 1051, 1091, 1171, 1259, 1319, 1399, 1439, 1451, 1459, 1499, 1531, 1559, 1571, 1619, 1759, 1811, 1831

Offset: 1

Peter K. Pearson (ppearson+att(AT)spamcop.net), May 06 2005

nonn

This is a sister sequence to A000057, because this sequence, since {k : A001177(k) = k-1}, might be called a subdiagonal sequence of A001177, and {k : A001177(k) = k+1}, which might be called a superdiagonal sequence of A001177. Sequences A000057 and A106535 are disjoint. Is this sequence the set of all divisors of some family of sequences, like A000057 is? - Art DuPre, Jul 11 2012
Are all members of this sequence prime? Using A069106, any composite members must exceed 89151931. - Robert Israel, Oct 13 2015
From Jianing Song, Jul 02 2019: (Start)
Yes, all terms are primes. See a brief proof below.
Also, if p == 1 (mod 4) then b(p) divides (p-Legendre(p,5))/2. So terms in this sequence are congruent to 11 or 19 modulo 20.
Primes p such that ord(-(3+sqrt(5))/2,p) = p-1, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer. (End)
Comments from Amiram Eldar, Jan 30 2022 (Start)
Sequence A003147, "Primes p with a Fibonacci primitive root", is defined in the paper: Daniel Shanks, Fibonacci primitive roots, Fibonacci Quarterly, Vol.  10, No. 2 (1972), pp. 163-168, and 181.
A second paper on this subject Daniel Shanks and Larry Taylor, An Observation of Fibonacci Primitive Roots, Fibonacci Quarterly, Vol. 11, No. 2 (1973), pp. 159-160,
deals with terms p == 3 (mod 4) of A003147, i.e., the intersection of A003147 and A002145 (or A004767).
It states that if g is a Fibonacci primitive root of a prime p such that p == 3 (mod 4) then g-1 and g-2 are also primitive roots of p.
The first 2000 terms of (A003147 intersect A002145) agree with the present sequence, although the definitions are quite different. Are these two sequences the same? (End)

Robert Israel, Table of n, a(n) for n = 1..2000
Alfred Brousseau, Primes which are factors of all Fibonacci sequences, Fib. Quart., 2 (1964), 33-38.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972.
Jianing Song, Proof that all terms are prime

Cf. A000057, A001175, A069106.

Similar sequences that give primes p such that A001177(p) = (p-1)/s: this sequence (s=1), A308795 (s=2), A308796 (s=3), A308797 (s=4), A308798 (s=5), A308799 (s=6), A308800 (s=7),A308801 (s=8), A308802 (s=9).

Filtered([2..2000], n -> Fibonacci(n-1) mod n = 0 and Filtered( [2..n-2], x -> Fibonacci(x) mod n = 0 ) = [] );

A106535 := proc(n)
        option remember;
        if n = 1 then
                11;
        else
                for a from procname(n-1)+1 do
                        if A001177(a) = a-1 then
                                return a;
                        end if;
                end do:
        end if;
end proc: # R. J. Mathar, Jul 09 2012
# Alternative:
fmod:= proc(a,b) local A;
  uses LinearAlgebra[Modular];
  A:= Mod(b, <<1,1>|<1,0>>,integer[8]);
  MatrixPower(b,A,a)[1,2];
end proc:
filter:= proc(n)
  local cands;
  if fmod(n-1,n) <> 0 then return false fi;
  cands:= map(t -> (n-1)/t, numtheory:-factorset(n-1));
  andmap(c -> (fmod(c,n) > 0), cands);
end proc:
select(filter, [$2..10^4]); # Robert Israel, Oct 13 2015

f[n_] := Block[{x = 2}, While[Mod[Fibonacci@ x, n] != 0, x++]; x];Select[Range@ 1860, f@ # == # - 1 &] (* Michael De Vlieger, Oct 13 2015 *)

isok(n) = {x = 2; while(fibonacci(x) % n, x++); x == n-1;} \\ Michel Marcus, Oct 20 2015

{n: A001177(n) = n-1}. - R. J. Mathar, Jul 09 2012

Corrected by T. D. Noe, Oct 25 2006

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

A094401 Composite n such that n divides both Fibonacci(n-1) and Fibonacci(n) - 1.

Original entry on oeis.org

2737, 4181, 6721, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 90061, 96049, 97921, 118441, 146611, 163081, 179697, 186961, 194833, 197209, 219781, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 327313, 330929

Offset: 1

Eric Rowland, May 01 2004

nonn

Composite n such that Q^(n-1) = I (mod n), where Q is the Fibonacci matrix {{1,1},{1,0}} and I is the identity matrix. The identity is also true for the primes congruent to 1 or 4 (mod 5), which is sequence A045468. The period of Q^k (mod n) is the same as the period of the Fibonacci numbers F(k) (mod n), A001175. Hence the terms in this sequence are the composite n such that A001175(n) divides n-1. [T. D. Noe, Jan 09 2009]

Giovanni Resta, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)
Eric Weisstein, MathWorld: Fibonacci Q-Matrix.

Cf. A005845, A069106, A094394, A094400.

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

More terms from Ryan Propper, Sep 24 2005

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

A100992 Indices k of Fibonacci numbers F(k) (A000045) that are divisible by k+1.

Original entry on oeis.org

10, 18, 28, 30, 40, 58, 60, 70, 78, 88, 100, 108, 130, 138, 148, 150, 178, 180, 190, 198, 210, 228, 238, 240, 250, 268, 270, 280, 310, 330, 348, 358, 378, 388, 400, 408, 418, 420, 430, 438, 441, 448, 460, 478, 490, 498, 508, 520, 540, 568, 570, 598, 600, 618

Offset: 1

Ron Knott, Nov 25 2004

nonn

When k+1 is prime, it is in A045468; when k+1 is composite (such as 442), it is in A069106. - T. D. Noe, Dec 13 2004

			18 is a term because F(18) = 2584 = 2*2*2*17*19 is divisible by 19, one more than its index number 18.

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

Cf. A000045, A100993, A023162, A023173, A045468, A069106.

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

More terms from Robert G. Wilson v, Nov 26 2004

A094409 Odd numbers k that divide Fibonacci(k) - 1 but not Fibonacci(k-1).

Original entry on oeis.org

323, 6479, 7743, 11663, 18407, 19043, 23407, 27071, 34943, 35207, 39203, 44099, 47519, 51983, 53663, 54839, 65471, 72831, 78089, 79547, 82983, 86063, 94667, 104663, 109871, 121103, 139359, 142883, 157079, 168299, 195227, 196559

Offset: 1

Eric Rowland, May 01 2004

nonn

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

Cf. A069106, A094394, A094410.

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

Offset corrected by Giovanni Resta, Jul 20 2013

A094410 Numbers k that divide Fibonacci(k-1) but do not divide Fibonacci(k) - 1.

Original entry on oeis.org

442, 1891, 6601, 8149, 13981, 17119, 17711, 30889, 40501, 52701, 68101, 78409, 88601, 88831, 115231, 138601, 145351, 150121, 153781, 191351, 199801, 218791, 265881, 266071, 316561, 332949, 342271, 348517, 407353, 453151, 456301, 464101

Offset: 1

Eric Rowland, May 01 2004

nonn

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

Cf. A000045, A069106, A094394, A094409.

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

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

More terms from David Wasserman, May 08 2007

A177086 Semiprimes k that divide Fibonacci(k-1).

Original entry on oeis.org

1891, 4181, 8149, 13201, 15251, 17711, 40501, 51841, 64079, 64681, 67861, 68251, 78409, 88601, 88831, 90061, 96049, 97921, 115231, 118441, 145351, 146611, 153781, 191351, 197209, 218791, 219781, 254321, 272611, 302101, 303101

Offset: 1

Jonathan Vos Post, Dec 09 2010

This is the semiprime (A001358) analog of A045468. Now A045468 has a very simple characterization: it consists of the primes ending in 1 or 9. Can one say anything about the present sequence?

			46368/23 = 2016 = 2^5 * 3^2 * 7 so (24-1) | Fibonacci(24) but 24 is not semiprime, so is not in the sequence.
a(1) = 1891 = 31 * 61 is not in the sequence because 1891 divides Fibonacci(1891-1) = Fibonacci(1890).
a(21) = 146611 = 271 * 541 because 146611 | Fibonacci(146610).

Chai Wah Wu, Table of n, a(n) for n = 1..837

Cf. A000040, A000045, A001358, A069106, A045468, A003631, A064739, A081264 (Fibonacci pseudoprimes).

Cf. A177745 (semiprimes k that divide Fibonacci(k+1)).

Select[Range[310000],PrimeOmega[#]==2 && Divisible[Fibonacci[#-1],#]&] (* Harvey P. Dale, May 02 2016 *)

{k: k is in A001358 and k|A000045(k-1)} = A069106 INTERSECTION A001358.

A177745 Semiprimes k that divide Fibonacci(k+1).

Original entry on oeis.org

323, 377, 3827, 5777, 10877, 11663, 18407, 19043, 23407, 25877, 27323, 34943, 39203, 51983, 53663, 60377, 75077, 86063, 94667, 100127, 113573, 121103, 121393, 161027, 162133, 182513, 195227, 200147, 231703, 240239, 250277, 294527, 306287, 345913, 381923, 429263, 430127, 454607, 500207, 507527, 548627, 569087, 600767, 635627, 636707, 685583, 697883, 736163, 753377, 775207, 828827, 851927, 948433, 983903

Offset: 1

Jonathan Vos Post, Dec 12 2010

Data from T. D. Noe.

			a(1) = 323 = 17 * 19 because it is semiprime (product of two prime A000040), and 323 divides F(324) = 23041483585524168262220906489642018075101617466780496790573690289968, with dividend 2^4 * 3^5 * 53 * 107 * 109 * 2269 * 3079 * 4373 * 5779 * 19441 * 11128427 * 62650261 * 1828620361 * 6782976947987.

Cf. A177086, A000045, A001358, A069106, A045468, A003631, A064739, A081264 (Fibonacci pseudoprimes).

With[{semis=Select[Range[1000000],PrimeOmega[#]==2&]},Select[semis, Divisible[Fibonacci[#+1],#]&]] (* Harvey P. Dale, Aug 20 2012 *)

{k: k is in A001358 and k|A000045(k+1)}.

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

A106535 Numbers k such that the smallest x > 1 for which Fibonacci(x) == 0 mod k is x = k - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A094401 Composite n such that n divides both Fibonacci(n-1) and Fibonacci(n) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A100992 Indices k of Fibonacci numbers F(k) (A000045) that are divisible by k+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A094409 Odd numbers k that divide Fibonacci(k) - 1 but not Fibonacci(k-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A094410 Numbers k that divide Fibonacci(k-1) but do not divide Fibonacci(k) - 1.

Views