A085014 -id:A085014 - cp's OEIS frontend

A214305 Fermat pseudoprimes to base 2 with two prime factors.

341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 14491, 15709, 18721, 19951, 23377, 31417, 31609, 31621, 35333, 42799, 49141, 49981, 60701, 60787, 65077, 65281, 80581, 83333, 85489, 88357, 90751, 104653, 123251, 129889, 130561

Offset: 1

Marius Coman, Jul 12 2012

nonn

This sequence is the same as A050217 for the first 60 terms and starts to differ at the 61st.
Conjecture: For any biggest prime factor of a Poulet number p1 with two prime factors, there exists a series with infinitely many Poulet numbers p2 formed this way: p2 mod (p1 - d) = d, where d is the biggest prime factor of p1. Note: it can be seen that the Poulet numbers divisible by 73 bigger than 2701 (7957, 10585, 15841, 31609, etc.) can be written as 1314*n + 73 as well as 2628*m + 73.
Conjecture: Any Poulet number p2 divisible by d can be written as (p1 - d)*n + d, where n is a positive integer, if there exists a smaller Poulet number p1 with two prime factors divisible by d.
Note: This conjecture can't be extrapolated for Poulet numbers p1 with more than two prime factors; for instance, if p1 = 561 = 3*11*17, there indeed are bigger Poulet numbers divisible by 17 (such as 1105 and 4369) that can be written as 544*n + 17, but there also exist such numbers that can't be written this way, e.g., 2465. But the first conjecture can be extrapolated.
Conjecture: For any biggest prime factor of a Poulet number p1 exists a series with infinitely many Poulet numbers p2 formed this way: p2 mod (p1 - d) = d, where d is the biggest prime factor of p1.
For each prime p, there are only a finite number of q such that p*q is here. See A085014. Sequence A180471 lists the factors of terms of this sequence. - T. D. Noe, Sep 20 2012
Numbers n = p*q such that n divides 2^(p-1)-1 and 2^(q-1)-1, where p,q are primes; thus 2^gcd(p-1,q-1) == 1 (mod n). - Thomas Ordowski, Aug 27 2016
These are semiprimes p*q such that 2^(p+q-2) == 1 (mod p*q). Proof: 2^(p-1) == 1 (mod p) and 2^(q-1) == 1 (mod q), so 2^((p-1)*(q-1)) == 1 (mod p*q), and (p-1)*(q-1) = (p*q-1)-(p+q-2). - Amiram Eldar and Thomas Ordowski, Apr 02 2021

			Few examples for the first 4 Poulet numbers with two prime factors:
For p1 = 341 = 11*31, the following Poulet numbers p2 for which p2 mod 310 = 31 were obtained: 2821, 4371, 4681, 10261 etc.
For p1 = 1387 = 19*73, the following Poulet numbers p2 for which p2 mod 1314 = 73 were obtained: 2701, 7957, 10585, 15841 etc.
For p1 = 2047 = 23*89, the following Poulet numbers p2 for which p2 mod 1958 = 89 were obtained: 31417, 35333, 60787, 62745 etc.
For p1 = 2701 = 37*73, the following Poulet numbers p2 for which p2 mod 2628 = 73 were obtained: 7957, 10585, 15841 etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 3299 terms from T. D. Noe)
Marius Coman, Conjecture that states that a Mersenne number with odd exponent is either prime either divisible by a 2-Poulet number, 2015.
Eric Weisstein's World of Mathematics, Poulet Number.
Index entries for sequences related to pseudoprimes

Subsequence of A050217.

Cf. A001567.

SemiPrimeQ[n_Integer] := If[Abs[n] < 2, False, (2 == Plus @@ Transpose[FactorInteger[Abs[n]]][[2]])]; Select[Range[200000], SemiPrimeQ[#] && PowerMod[2, #-1, #] == 1 &] (* T. D. Noe, Jul 12 2012 *)

list(lim)=my(v=List());forprime(p=31,lim\11, forprime(q=11,min(p-1,lim\p), if(Mod(2,p)^(q-1)==1 && Mod(2,q)^(p-1)==1, listput(v,p*q)))); if(lim>=1093^2,listput(v,1093^2)); if(lim>=3511^2,listput(v,3511^2)); vecsort(Vec(v)) \\ Charles R Greathouse IV, Sep 20 2012

A085012 For p = prime(n), a(n) is the smallest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

Original entry on oeis.org

0, 0, 0, 31, 0, 257, 73, 89, 113, 11, 73, 61681, 127, 178481, 157, 233, 1321, 20857, 281, 19, 2731, 13367, 23, 193, 601, 307, 6361, 37, 29, 43, 2731, 953, 168749965921, 593, 31, 53, 2593, 499, 101653, 62020897, 54001, 2281, 97, 19707683773, 5347, 29191

Offset: 2

T. D. Noe, Jun 28 2003

nonn

Using a construction in Erdős's paper, it can be shown that every odd prime except 3, 5, 7 and 13 is a factor of some 2-factor pseudoprime. Note that the cofactor q can be very large; for p=317, the smallest is 381364611866507317969. Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. The sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.

			a(11) = 11 because prime(11) = 31 and 11 is the smallest factor of 2^30-1 that yields a pseudoprime when multiplied by 31.

Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Amiram Eldar, Table of n, a(n) for n = 2..619
Amiram Eldar, Table of n, a(n) for n = 2..1000 with 2 missing terms (marked with value 0)
Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.
Index entries for sequences related to pseudoprimes

Cf. A001567 (base-2 pseudoprimes), A085014, A086019, A180471.

Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; i=1; While[i<=Length[q] && (PowerMod[2, p*q[[i]]-1, p*q[[i]]]>1), i++ ]; If[i>Length[q], 0, q[[i]]], {n, 2, 56}]

A180471 Irregular triangle in which row n has all primes q such that prime(n)*q is a base-2 Fermat pseudoprime.

Original entry on oeis.org

31, 257, 73, 89, 683, 113, 11, 151, 331, 73, 109, 61681, 127, 337, 5419, 178481, 2796203, 157, 1613, 233, 1103, 2089, 3033169, 1321, 20857, 599479, 281, 86171, 122921, 19, 37, 109, 433, 38737, 2731, 8191, 121369, 22366891, 13367, 164511353, 8831418697, 23, 353, 397, 683, 2113, 2931542417

Offset: 5

T. D. Noe, Jan 19 2011

The length of row n is A085014(n). The smallest and largest primes in row n are A085012(n) and A085019(n).

			The irregular triangle begins
31
none
257
73
89, 683
113
11, 151, 331
73, 109
61681

See A085012.

Amiram Eldar, Table of n, a(n) for n = 5..3424
Index entries for sequences related to pseudoprimes

Cf. A085012, A085014, A085019.

Flatten[Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; cnt={}; Do[If[PowerMod[2, p*q[[i]]-1, p*q[[i]]]==1, AppendTo[cnt,q[[i]]]], {i,Length[q]}]; cnt, {n,5,50}]]

A086019 For p = prime(n), a(n) is the largest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

Original entry on oeis.org

0, 0, 0, 31, 0, 257, 73, 683, 113, 331, 109, 61681, 5419, 2796203, 1613, 3033169, 1321, 599479, 122921, 38737, 22366891, 8831418697, 2931542417, 22253377, 268501, 131071, 28059810762433, 279073, 54410972897, 77158673929, 145295143558111

Offset: 2

T. D. Noe, Jul 08 2003

Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. Sequence A085012 gives the smallest prime q such that 2^(pq-1) = 1 mod pq. Sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

			a(9) = 683 because prime(9) = 23 and 683 is the largest factor of 2^22-1 that yields a pseudoprime when multiplied by 23.

Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Amiram Eldar, Table of n, a(n) for n = 2..337
Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.

Cf. A001567 (base 2 pseudoprimes), A085012, A085014, A180471.

Table[p=Prime[n]; q=Reverse[Transpose[FactorInteger[2^(p-1)-1]][[1]]]; i=1; While[i<=Length[q]&&(PowerMod[2, p*q[[i]]-1, p*q[[i]]]>1), i++ ]; If[i>Length[q], 0, q[[i]]], {n, 2, 40}]

cp's OEIS Frontend

A214305 Fermat pseudoprimes to base 2 with two prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A085012 For p = prime(n), a(n) is the smallest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A180471 Irregular triangle in which row n has all primes q such that prime(n)*q is a base-2 Fermat pseudoprime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A086019 For p = prime(n), a(n) is the largest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica