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

A094395 Odd composite n such that n divides Fibonacci(n) + 1.

Original entry on oeis.org

5777, 10877, 17261, 75077, 80189, 100127, 113573, 120581, 161027, 162133, 163059, 231703, 300847, 430127, 618449, 635627, 667589, 851927, 1033997, 1106327, 1256293, 1388903, 1697183, 1842581, 2263127, 2435423, 2512889, 2662277

Offset: 1

Eric Rowland, May 01 2004

nonn

For each prime p, Fibonacci(p) = 5^((p-1)/2) mod p, so p divides Fibonacci(p) + 1 for each prime p=10k+-3. Hence it is interesting to seek also nonprimes with the same property, a motivation for this sequence. - Robert FERREOL, Jul 14 2015
Are all terms squarefree? A counterexample can't be divisible by the square of a prime < 1000. - Robert Israel, Jul 17 2015
Any term that is not squarefree must be divisible by the square of a Fibonacci-Wieferich prime (see the StackExchange link). There are believed to be infinitely many such primes, but none are known, and none are less than 2*10^14. - Robert Israel, Jul 22 2015

Giovanni Resta, Table of n, a(n) for n = 1..579 (terms < 4*10^9)
R. Israel and N. Elkies, Fibonacci == -1 mod p^2, Mathematics StackExchange, July 2015.
R. J. McIntosh and E. L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp. 76 (2007), 2087-2094.

Cf. A005845, A094394.

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[3, 300000, 2], !PrimeQ[ # ] && Mod[Fibonacci[ # ] + 1, # ] == 0 &]

main(size)=my(v=vector(size),i,t=1); for(i=1,size, while(1, if(t%2==1&&omega(t)>1&&(fibonacci(t)+1)%t==0, v[i]=t; break, t++)); t++); v; \\ Anders Hellström, Jul 17 2015

is(n)=((Mod([1,1;1,0],n))^n)[1,2]==-1 && n%2 && !isprime(n) \\ Charles R Greathouse IV, Jul 20 2015

a(6)-a(14) from Robert G. Wilson v, May 01 2004

More terms from Ryan Propper, Aug 03 2005

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

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

Original entry on oeis.org

35, 169, 385, 899, 961, 1121, 2001, 3107, 4879, 4901, 5719, 6215, 6265, 6441, 6479, 6601, 7055, 7801, 8119, 8339, 9799, 10403, 10763, 10945, 13079, 13601, 15841, 18241, 19097, 20833, 20951, 22499, 24727, 27839, 29183, 29953, 30731, 31417, 31535, 34561, 37345

Offset: 1

Jon E. Schoenfield, Sep 08 2018

nonn

It appears that most of the terms of A319040 (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 A319043.

			k=35 is in the sequence: Pell(35) = 8822750406821 = 35*252078583052 + 1 == 1 (mod 35).
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..500

Cf. A000129 (Pell numbers), A094394, A319040, A319041, A319043.

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

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

Original entry on oeis.org

4181, 6721, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 90061, 96049, 97921, 118441, 146611, 163081, 186961, 197209, 219781, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 330929, 399001, 433621, 438751, 489601, 512461, 520801

Offset: 1

Jianing Song, Sep 12 2018

nonn

Complement of A212423 with respect to A212424.
Intersection of A212424 and A047209.
Composite k == 1,4 (mod 5) such that Fibonacci(k) == 1 (mod k) and that k divides Fibonacci(k-1).

			4181 = 37*113 is composite, while Fibonacci(4180) == 0 (mod 4181), Fibonacci(4181) == 1 (mod 4181), so 4181 is a term.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (from Dana Jacobsen's site)
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.
A. Rotkiewicz, Lucas and Frobenius Pseudoprimes, Annales Mathematicae Silesiane, 17 (2003): 17-39.
Eric Weisstein's World of Mathematics, Frobenius Pseudoprime.

Cf. A047209, A093372, A094394, A094401, A212423, A212424.

for(n=2,500000,if(!isprime(n) && (n%5==1||n%5==4) && fibonacci(n-kronecker(5,n))%n==0 && (fibonacci(n)-kronecker(5,n))%n==0, print1(n, ", ")))

A345753 Euler-Fibonacci pseudoprimes: odd composites k such that F(k) == 5^((k-1)/2) == +-1 (mod k), where F(k) = A000045(k), the Fibonacci numbers.

Original entry on oeis.org

146611, 252601, 399001, 512461, 556421, 852841, 1024651, 1193221, 1314631, 1857241, 1909001, 2100901, 2165801, 2603381, 2704801, 3470921, 3828001, 3942271, 4504501, 5049001, 5148001, 5481451, 6189121, 6840001, 7267051, 7519441, 7879681, 8086231, 8341201, 8719921, 9439201, 9863461

Offset: 1

Amiram Eldar and Thomas Ordowski, Jun 26 2021

nonn

If p is an odd prime except 5, then F(p) == 5^((p-1)/2) == +-1 (mod p).
All terms found satisfy the congruence F(k) == 5^((k-1)/2) == 1 (mod k). They are a proper subset of A094394.
Are there odd composites m such that F(m) == 5^((m-1)/2) == -1 (mod m)? They are a proper subset (maybe empty) of A094395 (they are not in the database, below 4*10^9).

Cf. A000045, A094394, A094395, A262052.

Select[Range[1, 10^6, 2], CompositeQ[#] && MemberQ[{1, # - 1}, PowerMod[5, (# - 1)/2, #]] && Divisible[5^((# - 1)/2) - Fibonacci[#], #] &]

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

A094395 Odd composite n such that n divides Fibonacci(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments