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

A327653 Composite numbers k coprime to 13 such that k divides A006190(k-Kronecker(13,k)).

Original entry on oeis.org

10, 119, 649, 1189, 1763, 3599, 4187, 5559, 6681, 12095, 12403, 12685, 12871, 12970, 14041, 14279, 15051, 16109, 19043, 22847, 23479, 24769, 26795, 28421, 30743, 30889, 31631, 31647, 33919, 34997, 37949, 38503, 39203, 41441, 46079, 48577, 49141, 50523, 50545, 53301, 56279, 58081, 58589

Offset: 1

Jianing Song, Sep 20 2019

nonn

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n) = m*x(n-1) + x(n-2) for k >= 2. For primes p, we have (a) p divides x(p-((m^2+4)/p)); (b) x(p) == ((m^2+4)/p) (mod p), where (D/p) is the Kronecker symbol. This sequence gives composite numbers k such that gcd(k, m^2+4) = 1 and that a condition similar to (a) holds for k, where m = 3.
If k is not required to be coprime to m^2 + 4 (= 13), then there are 360 such k <= 10^5 and 1506 such k <= 10^6, while there are only 62 terms <= 10^5 and 197 terms <= 10^6 in this sequence.
Also composite numbers k coprime to 13 such that A322907(k) divides k - Kronecker(13,k).

			A006190(9) = 12970 which is divisible by 10, so 10 is a term.

Amiram Eldar, Table of n, a(n) for n = 1..10000

             m                      m=1            m=2      m=3
k | x(k-Kronecker(m^2+4,k))*  A081264 U A141137  A327651  this seq
k | x(k)-Kronecker(m^2+4,k)        A049062       A099011  A327654
            both                   A212424       A327652  A327655
* k is composite and coprime to m^2 + 4.
Cf. A006190, A322907, A011583 ({Kronecker(13,n)}).

seqmod(n, m)=((Mod([3, 1; 1, 0], m))^n)[1, 2]
isA327653(n)=!isprime(n) && !seqmod(n-Kronecker(13,n), n) && gcd(n,13)==1 && n>1

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

A327651 Composite numbers k coprime to 8 such that k divides Pell(k - Kronecker(8,k)), Pell = A000129.

Original entry on oeis.org

35, 169, 385, 779, 899, 961, 1121, 1189, 2419, 2555, 2915, 3107, 3827, 6083, 6265, 6441, 6601, 6895, 6965, 7801, 8119, 8339, 9179, 9809, 9881, 10403, 10763, 10835, 10945, 13067, 14027, 14111, 15179, 15841, 18241, 18721, 19097, 20833, 20909, 22499, 23219, 24727, 26795, 27869, 27971

Offset: 1

Jianing Song, Sep 20 2019

nonn

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n) = m*x(n-1) + x(n-2) for k >= 2. For primes p, we have (a) p divides x(p-((m^2+4)/p)); (b) x(p) == ((m^2+4)/p) (mod p), where (D/p) is the Kronecker symbol. This sequence gives composite numbers k such that gcd(k, m^2+4) = 1 and that a condition similar to (a) holds for k, where m = 2.
If k is not required to be coprime to m^2 + 4 (= 8), then there are 1232 such k <= 10^5 and 4973 such k <= 10^6, while there are only 83 terms <= 10^5 and 245 terms <= 10^6 in this sequence.
Also composite numbers k coprime to 8 such that A214028(k) divides k - Kronecker(8,k).

			Pell(36) = 21300003689580 is divisible by 35, so 35 is a term.

Amiram Eldar, Table of n, a(n) for n = 1..10000

             m                       m=1           m=2       m=3
k | x(k-Kronecker(m^2+4,k))*  A081264 U A141137  this seq  A327653
k | x(k)-Kronecker(m^2+4,k)        A049062       A099011   A327654
            both                   A212424       A327652   A327655
* k is composite and coprime to m^2 + 4.
Cf. A000129, A214028, A091337 ({Kronecker(8,n)}).

pellmod(n, m)=((Mod([2, 1; 1, 0], m))^n)[1, 2]
isA327651(n)=!isprime(n) && !pellmod(n-kronecker(8,n), n) && gcd(n,8)==1 && n>1

A327652 Intersection of A099011 and A327651.

Original entry on oeis.org

169, 385, 961, 1121, 3827, 6265, 6441, 6601, 7801, 8119, 10945, 13067, 15841, 18241, 19097, 20833, 24727, 27971, 29953, 31417, 34561, 35459, 37345, 38081, 39059, 42127, 45961, 47321, 49105, 52633, 53041, 55969, 56953, 58241, 62481, 74305, 79361, 81361, 84587, 86033, 86241, 101311, 107801

Offset: 1

Jianing Song, Sep 20 2019

nonn

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n) = m*x(n-1) + x(n-2) for k >= 2. For primes p, we have (a) p divides x(p-((m^2+4)/p)); (b) x(p) == ((m^2+4)/p) (mod p), where (D/p) is the Kronecker symbol. This sequence gives composite numbers k such that gcd(k, m^2+4) = 1 and that conditions similar to (a) and (b) hold for k simultaneously, where m = 2.

If k is not required to be coprime to m^2 + 4 (= 8), then there are 1190 such k <= 10^5 and 4847 such k <= 10^6, while there are only 41 terms <= 10^5 and 119 terms <= 10^6 in this sequence.

			169 divides Pell(168) as well as Pell(169) - 1, so 169 is a term.

Daniel Suteu, Table of n, a(n) for n = 1..10000

             m                       m=1           m=2       m=3
k | x(k-Kronecker(m^2+4,k))*  A081264 U A141137  A327651   A327653
k | x(k)-Kronecker(m^2+4,k)        A049062       A099011   A327654
            both                   A212424       this seq  A327655
* k is composite and coprime to m^2 + 4.
Cf. A000129, A091337 ({Kronecker(8,n)}).

pellmod(n, m)=((Mod([2, 1; 1, 0], m))^n)[1, 2]
isA327652(n)=!isprime(n) && pellmod(n, n)==kronecker(8,n) && !pellmod(n-kronecker(8,n), n) && gcd(n,8)==1 && n>1

A327654 Composite numbers k coprime to 13 such that k divides A006190(k) - Kronecker(13,k).

Original entry on oeis.org

4, 8, 9, 119, 399, 649, 1023, 1179, 1189, 1199, 1881, 2703, 3519, 4081, 4187, 5151, 7055, 7361, 10349, 12871, 13833, 14041, 15519, 16109, 18639, 22593, 23479, 24769, 26937, 28421, 29007, 31631, 34111, 34997, 38503, 41441, 44671, 48577, 50545, 51711, 53823, 56279, 57407, 58081, 59081

Offset: 1

Jianing Song, Sep 20 2019

nonn

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n) = m*x(n-1) + x(n-2) for k >= 2. For primes p, we have (a) p divides x(p-((m^2+4)/p)); (b) x(p) == ((m^2+4)/p) (mod p), where (D/p) is the Kronecker symbol. This sequence gives composite numbers k such that gcd(k, m^2+4) = 1 and that a condition similar to (b) holds for k, where m = 3.

If k is not required to be coprime to m^2 + 4 (= 13), then there are 352 such k <= 10^5, and 1457 such k <= 10^6, while there are only 54 terms <= 10^5 and 148 terms <= 10^6 in this sequence.

			A006190(8) = 3927 == Kronecker(13,8) (mod 8), so 8 is a term.

Amiram Eldar, Table of n, a(n) for n = 1..2000

             m                      m=1            m=2      m=3
k | x(k-Kronecker(m^2+4,k))*  A081264 U A141137  A327651  A327653
k | x(k)-Kronecker(m^2+4,k)        A049062       A099011  this seq
            both                   A212424       A327652  A327655
* k is composite and coprime to m^2 + 4.
Cf. A006190, A011583 ({Kronecker(13,n)}).

seqmod(n, m)=((Mod([3, 1; 1, 0], m))^n)[1, 2]
isA327654(n)=!isprime(n) && seqmod(n, n)==kronecker(13,n) && gcd(n,13)==1 && n>1

A327655 Intersection of A327653 and A327654.

Original entry on oeis.org

119, 649, 1189, 4187, 12871, 14041, 16109, 23479, 24769, 28421, 31631, 34997, 38503, 41441, 48577, 50545, 56279, 58081, 59081, 61447, 75077, 91187, 95761, 96139, 116821, 127937, 146329, 148943, 150281, 157693, 170039, 180517, 188501, 207761, 208349, 244649, 281017, 311579, 316409

Offset: 1

Jianing Song, Sep 20 2019

nonn

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n) = m*x(n-1) + x(n-2) for k >= 2. For primes p, we have (a) p divides x(p-((m^2+4)/p)); (b) x(p) == ((m^2+4)/p) (mod p), where (D/p) is the Kronecker symbol. This sequence gives composite numbers k such that gcd(k, m^2+4) = 1 and that conditions similar to (a) and (b) hold for k simultaneously, where m = 2.

If k is not required to be coprime to m^2 + 4 (= 13), then there are 322 such k <= 10^5 and 1381 such k <= 10^6, while there are only 24 terms <= 10^5 and 72 terms <= 10^6 in this sequence.

			119 divides A006190(120) as well as A006190(119) + 1, so 119 is a term.

             m                      m=1            m=2      m=3
k | x(k-Kronecker(m^2+4,k))*  A081264 U A141137  A327651  A327653
k | x(k)-Kronecker(m^2+4,k)        A049062       A099011  A327654
            both                   A212424       A327652  this seq
* k is composite and coprime to m^2 + 4.
Cf. A006190, A011583 ({Kronecker(13,n)}).

seqmod(n, m)=((Mod([3, 1; 1, 0], m))^n)[1, 2]
isA327655(n)=!isprime(n) && seqmod(n, n)==kronecker(13,n) && !seqmod(n-kronecker(13,n), n) && gcd(n,13)==1 && n>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

A327653 Composite numbers k coprime to 13 such that k divides A006190(k-Kronecker(13,k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Perl

A327651 Composite numbers k coprime to 8 such that k divides Pell(k - Kronecker(8,k)), Pell = A000129.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A327652 Intersection of A099011 and A327651.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A327654 Composite numbers k coprime to 13 such that k divides A006190(k) - Kronecker(13,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A327655 Intersection of A327653 and A327654.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI