A094395 -id:A094395 - cp's OEIS frontend

A005845 Bruckman-Lucas pseudoprimes: k | (L_k - 1), where k is composite and L_k = Lucas numbers A000032.

705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, 24465, 29281, 34561, 35785, 51841, 54705, 64079, 64681, 67861, 68251, 75077, 80189, 90061, 96049, 97921, 100065, 100127, 105281, 113573, 118441, 146611, 161027

Offset: 1

N. J. A. Sloane

This uses the definition of "Lucas pseudoprime" by Bruckman, not the one by Baillie and Wagstaff. - R. J. Mathar, Jul 15 2012
Unlike the earlier Baillie-Wagstaff Lucas pseudoprimes A217120, these have significant overlap with the Fermat primality test. For example, the number 82380774001 is both an A005845 Lucas pseudoprime and a Fermat pseudoprime to the first 407 prime bases. - Dana Jacobsen, Jan 10 2015
k in A002808 such that A213060(k) = 1. - Robert Israel, Jul 14 2015

Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 104.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 105.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Somer, Lawrence. "Generalization of a Theorem of Bruckman on Dickson Pseudoprimes." Fibonacci Quarterly 60:4 (2022), 357-361.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (from Dana Jacobsen's site, terms 1..1000 from T. D. Noe)
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.
R. Baillie and S. S. Wagstaff, Lucas pseudoprimes, Math. Comp 35 (1980) 1391-1417.
P. S. Bruckman, Lucas Pseudoprimes are odd, Fib. Quart. 32 (1994), 155-157.
Dana Jacobsen, Pseudoprime Statistics, Tables, and Data.
Eric Weisstein's World of Mathematics, Lucas Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A000032, A002808.
Cf. A094394, A094395 (analogous numbers with the Fibonacci sequence). - Robert FERREOL, Jul 14 2015
Cf. A213060 (L(n) mod n).

a005845 n = a005845_list !! (n-1)
a005845_list = filter (\x -> (a000032 x - 1) `mod` x == 0) a002808_list
-- Reinhard Zumkeller, Nov 13 2014

with(combinat):lucas:=n->fibonacci(n-1)+fibonacci(n+1):
test:=n->lucas(n) mod n=1:select(test and not isprime,[seq(n,n=1..10000)]); # Robert FERREOL, Jul 14 2015

Select[Range[2,170000],!PrimeQ[#]&&Divisible[LucasL[#]-1,#]&] (* Harvey P. Dale, Mar 08 2014 *)

is(n)=my(M=Mod([1,1;1,0],n)^n);M[1,1]+M[2,2]==1 && !isprime(n) && n>1 \\ Charles R Greathouse IV, Dec 27 2013

from sympy import isprime
from itertools import count, islice
def agen(): # generator of terms
    L0, L1 = 2, 1
    for k in count(1):
        L0, L1 = L1, L0+L1
        if k > 1 and not isprime(k) and (L0-1)%k == 0:
            yield k
print(list(islice(agen(), 32))) # Michael S. Branicky, Apr 07 2024

More terms from David Broadhurst

A094394 Odd composites m that divide Fibonacci(m)-1.

Original entry on oeis.org

323, 2737, 4181, 6479, 6721, 7743, 11663, 13201, 15251, 18407, 19043, 23407, 27071, 34561, 34943, 35207, 39203, 44099, 47519, 51841, 51983, 53663, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 78089, 79547, 82983, 86063, 90061, 94667

Offset: 1

Eric Rowland, May 01 2004

nonn

No terms satisfy the Fermat criterion 2^(a(n)-1) mod a(n) = 1. - Gary Detlefs, May 25 2014

For each prime p, Fibonacci(p) = 5^((p-1)/2) mod p, so p divides Fibonacci(p) - 1 for each prime p=10k+-1. Hence it is interesting to seek also nonprimes with the same property, a motivation for this sequence. - Robert FERREOL, Jul 14 2015

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

Cf. A094395, A094400.

with(combinat):test:=n->(fibonacci(n)-1) mod n= 0:
select(test and not isprime ,[seq(2*k+1,k=1..10000)]); # Robert FERREOL, Jul 14 2015

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

main(m)=forcomposite(n=1,m,if(((n%2==1)&&(fibonacci(n)-1)%n==0),print1(n,", "))); \\ Anders Hellström, Aug 12 2015

Offset corrected by Giovanni Resta, Jul 20 2013

A212424 Frobenius pseudoprimes with respect to Fibonacci polynomial x^2 - x - 1.

Original entry on oeis.org

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 75077, 90061, 96049, 97921, 100127, 113573, 118441, 146611, 161027, 162133, 163081, 186961, 197209, 219781, 231703, 252601, 254321, 257761, 268801, 272611

Offset: 1

Max Alekseyev, May 16 2012

nonn

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

R. Crandall, C. B. Pomerance. Prime Numbers: A Computational Perspective. Springer, 2nd ed., 2005.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (from Dana Jacobsen's site, terms 1..653 from Max Alekseyev)
Dorin Andrica and Ovidiu Bagdasar, Recurrent Sequences: Key Results, Applications, and Problems, Springer (2020), p. 89.
Jon Grantham, Frobenius pseudoprimes, Mathematics of Computation 70 (234): 873-891, 2001. doi: 10.1090/S0025-5718-00-01197-2.
Dana Jacobsen, Pseudoprime Statistics, Tables, and Data (includes terms through 10^13)
A. Rotkiewicz, Lucas and Frobenius Pseudoprimes, Annales Mathematicae Silesiane, 17 (2003): 17-39.
Lawrence Somer, Lucas sequences {Uk} for which U2p and Up are pseudoprimes for almost all primes p, Fibonacci Quart. 44 (2006), no. 1, 7-12.
Eric W. Weisstein, Frobenius Pseudoprime, MathWorld.

Cf. A049062, A081264, A141137.
Cf. also A005845, A094063, A094395, A094411.
Terms congruent to 2 or 3 mod 5 are given in A212423.

{ 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) }

use ntheory ":all"; foroddcomposites { say if is_frobenius_pseudoprime($,1,-1) } 1e10; # _Dana Jacobsen, Aug 05 2015

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

A182554 Composite numbers k that divide Fibonacci(k+1) or Fibonacci(k-1).

Original entry on oeis.org

323, 377, 442, 1891, 2737, 2834, 3827, 4181, 5777, 6479, 6601, 6721, 8149, 10877, 11663, 13201, 13981, 15251, 17119, 17711, 18407, 19043, 20999, 23407, 25877, 27323, 30889, 34561, 34943, 35207, 39203, 40501, 44099, 47519, 50183, 51841, 51983, 52701, 53663

Offset: 1

Gary Detlefs, May 04 2012

nonn

Pseudoprimes to a Fibonacci criterion for primality.
It is known that for prime p <> 5, Fibonacci(p-1) or Fibonacci(p+1) is divisible by p. (see Burton reference)
Primes for which Fibonacci(p-1) are divisible by p are congruent to {0,1,4} mod 5 and are listed in A038872.
Primes for which Fibonacci(p+1) are divisible by p are congruent to {2,3} mod 5 and are listed in A003631.
For n <= 1000, a(n) is squarefree (see A005117). - Dmitry Kamenetsky, Jul 20 2015
Any nonsquarefree term is divisible by the square of a Fibonacci-Wieferich prime (i.e., a prime p such that Fibonacci(j) == 0 (mod p^2) for some j not divisible by p). No Fibonacci-Wieferich primes are known, and there are none < 2*10^14, although it is conjectured that there are infinitely many. - Robert Israel, Jul 22 2015

David M. Burton, Elementary Number Theory, Allyn and Bacon, 1980, p. 292, #1.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Giovanni Resta)
R. J. McIntosh and E. L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp. 76 (2007), 2087-2094.

Cf. A038872, A003631, A000040, A094395, A005117.

with(combinat): f:= n-> fibonacci(n): for n from 1 to 40000 do if (f(n+1)/n = floor(f(n+1)/n) or f(n-1)/n=floor(f(n-1)/n)) and not isprime(n) then print(n) fi od;

Select[Range[50000], CompositeQ[#] && (Divisible[Fibonacci[# - 1], #] || Divisible[Fibonacci[# + 1], #]) &] (* Amiram Eldar, Sep 12 2022 *)

p=2;forprime(q=3,1e5,for(n=p+1,q-1,t=Mod([1,1;1,0],n)^(n-1);if(t[1,2]==0 || (t*[1,1;1,0]^2)[1,2]==0,print1(n", ")));p=q) \\ Charles R Greathouse IV, May 05 2012

A319043 Composite numbers k such that Pell(k) == -1 (mod k).

Original entry on oeis.org

741, 3827, 11395, 13067, 27971, 35459, 39059, 84587, 92833, 117739, 134579, 134945, 155819, 177497, 189419, 332949, 382771, 437579, 469699, 473891, 548627, 600059, 632269, 643259, 656083, 677379, 724883, 783579, 828827, 895299, 966779, 1015429, 1021987

Offset: 1

Jon E. Schoenfield, Sep 08 2018

nonn

It appears that most of the terms of A319041 (Numbers k such that Pell(k) == -1 (mod k)) are primes; this sequence lists the composites.
For the composite numbers k such that Pell(k) == 1 (mod k), see A319042.
Numbers that are terms of this sequence seem to be considerably less common than those in A319042; e.g., the numbers of terms in that sequence up to 10^3, 10^4, 10^5, and 10^6 are 5, 21, 67, and 200, respectively, while the corresponding term counts here are only 1, 2, 9, and 31. Why is this?

			k=741 is in the sequence: Pell(741) = 741*M - 1 == -1 (mod 741) (where M is a large integer).
k=6 is not in the sequence: Pell(6) = 70 = 6*12 - 2 !== -1 (mod 6).

Seiichi Manyama, Table of n, a(n) for n = 1..50

Cf. A000129 (Pell numbers), A094395, A319040, A319041, A319042.

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

A212423 Frobenius pseudoprimes == 2,3 (mod 5) with respect to Fibonacci polynomial x^2 - x - 1.

Original entry on oeis.org

5777, 10877, 75077, 100127, 113573, 161027, 162133, 231703, 430127, 635627, 851927, 1033997, 1106327, 1256293, 1388903, 1697183, 2263127, 2435423, 2662277, 3175883, 3399527, 3452147, 3774377, 3900797, 4109363, 4226777, 4403027, 4828277, 4870847

Offset: 1

Max Alekseyev, May 16 2012

nonn

Grantham incorrectly claims that "the first Frobenius pseudoprime with respect to the Fibonacci polynomial x^2 - x - 1 is 5777". However n = 5777 is the first Frobenius pseudoprime with respect to x^2 - x - 1 that has Jacobi symbol (5/n) = -1, i.e., n == 2,3 (mod 5). Unrestricted version with the first term 4181 is given in A212424.
Intersection of A212424 and A047221.
Composite k == 2,3 (mod 5) such that Fibonacci(k) == -1 (mod k) and that k divides Fibonacci(k+1). - Jianing Song, Sep 12 2018

R. Crandall, C. B. Pomerance. Prime Numbers: A Computational Perspective. Springer, 2nd ed., 2005.

Amiram Eldar, Table of n, a(n) for n = 1..14070 (terms below 10^13 from Dana Jacobsen's site)
Jon Grantham, Frobenius Pseudoprimes, Mathematics of Computation, 7 (2000), 873-891.
Dana Jacobsen, Pseudoprime Statistics, Tables, and Data.
Eric Weisstein's World of Mathematics, Frobenius Pseudoprime.

Cf. A047221, A094063, A094395, A094411, A212424.

{ isFP23(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) }

A094413 Odd composites k that divide Fibonacci(k) + 1 but not Fibonacci(k+1).

Original entry on oeis.org

17261, 120581, 163059, 300847, 1842581, 3489641, 3792541, 5573499, 21159271, 36561959, 40779991, 63055651, 67306519, 69503037, 72125899, 129487163, 136021717, 174008141, 175094767, 247600477, 418623283, 529281911, 814454381, 902315699

Offset: 1

Eric Rowland, May 07 2004

nonn

David Radcliffe, Table of n, a(n) for n = 1..33 (first 24 terms from G. Resta)

Cf. A094395, A094411, A094412.

isok(n) = (n % 2) && ! ((fibonacci(n) + 1) % n) && (fibonacci(n+1) % n); \\ Michel Marcus, Aug 27 2013

4 more terms from Ryan Propper, Aug 03 2005

a(9)-a(24) from Giovanni Resta, Jul 20 2013

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

A005845 Bruckman-Lucas pseudoprimes: k | (L_k - 1), where k is composite and L_k = Lucas numbers A000032.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Extensions

A094394 Odd composites m that divide Fibonacci(m)-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A212424 Frobenius pseudoprimes with respect to Fibonacci polynomial x^2 - x - 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Perl

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A182554 Composite numbers k that divide Fibonacci(k+1) or Fibonacci(k-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A319043 Composite numbers k such that Pell(k) == -1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A212423 Frobenius pseudoprimes == 2,3 (mod 5) with respect to Fibonacci polynomial x^2 - x - 1.

Views