A214305 -id:A214305 - cp's OEIS frontend

A300418 Number of semiprime Fermat pseudoprimes to base 2 (A214305) less than 10^n.

Original entry on oeis.org

0, 0, 1, 11, 34, 107, 312, 882, 2457, 6504, 17206, 46073, 123868, 334567, 915443, 2520503, 7002043, 19604493, 55264235

Offset: 1

Amiram Eldar, Mar 05 2018

Jan Feitsma, The pseudoprimes below 2^64 - statistics.
William F. Galway, The Density of Pseudoprimes with Two Prime Factors.
Aran Nayebi, On the distribution of Carmichael numbers, arXiv preprint arXiv:0906.3533 [math.NT], 2009-2013. But beware of errors!

Cf. A055550, A214305.

Corrected and extended by Daniel Suteu, Dec 10 2019

A050217 Super-Poulet numbers: Poulet numbers whose divisors d all satisfy d|2^d-2.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein

nonn

Every semiprime in A001567 is in this sequence (see Sierpiński). a(61) = 294409 is the first term having more than two prime factors. See A178997 for super-Poulet numbers having more than two prime factors. - T. D. Noe, Jan 11 2011
Composite numbers n such that 2^d == 2 (mod n) for every d|n. - Thomas Ordowski, Sep 04 2016
Composite numbers n such that 2^p == 2 (mod n) for every prime p|n. - Thomas Ordowski, Sep 06 2016
Composite numbers n = p(1)^e(1)*p(2)^e(2)*...*p(k)^e(k) such that 2^gcd(p(1)-1,p(2)-1,...,p(k)-1) == 1 (mod n). - Thomas Ordowski, Sep 12 2016
Nonsquarefree terms are divisible by the square of a Wieferich prime (see A001220). These include 1194649, 12327121, 5654273717, 26092328809, 129816911251. - Robert Israel, Sep 13 2016
Composite numbers n such that 2^A258409(n) == 1 (mod n). - Thomas Ordowski, Sep 15 2016

W. Sierpiński, Elementary Theory of Numbers, Warszawa, 1964, p. 231.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Eric Weisstein's World of Mathematics, Super-Poulet Numbers
Wikipedia, Super-Poulet number

A214305 is a subsequence.
A065341 is a subsequence. - Thomas Ordowski, Nov 20 2016
Cf. A001220, A001567, A178997.

filter:= = proc(n)
    not isprime(n) and andmap(p -> 2&^p mod n = 2, numtheory:-factorset(n))
end proc:
select(filter, [seq(i,i=3..10^5,2)]); # Robert Israel, Sep 13 2016

Select[Range[1, 110000, 2], !PrimeQ[#] && Union[PowerMod[2, Rest[Divisors[#]], #]] == {2} & ]

is(n)=if(isprime(n), return(0)); fordiv(n,d, if(Mod(2,d)^d!=2, return(0))); n>1 \\ Charles R Greathouse IV, Aug 27 2016

A316907 Numbers k such that 2^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

Original entry on oeis.org

7957, 23377, 35333, 42799, 49981, 60787, 129889, 150851, 162193, 164737, 241001, 249841, 253241, 256999, 280601, 318361, 452051, 481573, 556169, 580337, 617093, 665333, 722201, 838861, 877099, 1016801, 1251949, 1252697, 1325843, 1507963, 1534541, 1678541, 1826203, 1969417

Offset: 1

Thomas Ordowski, Jul 16 2018

nonn

Numbers k such that 2^k == 2 (mod k) and gcd(k,b^k-b) = 1 for some b > 2.
Problem: are there infinitely many such "anti-Carmichael pseudoprimes"?
All semiprime terms of A316906 are in the sequence; i.e., numbers m in A214305 such that p-1 does not divide q-1, where m = pq and p < q are primes.

			7957 = 73*109 is pseudoprime and 72 does not divide 7956 (of course also 108 does not divide 7956), note that 72 does not divide 108.
617093 = 43*113*127 is the smallest such pseudoprime with more than two prime factors.

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

Subsequence of A001567 and of A316906.

Cf. A121707 (probably "anti-Carmichael numbers": n such that p-1 does not divide n-1 for every prime p dividing n).

Select[Select[Range[2*10^6], PowerMod[2, # - 1, #] == 1 &], Function[k, AllTrue[FactorInteger[k][[All, 1]] - 1, Mod[k - 1, #] != 0 &]]] (* Michael De Vlieger, Jul 20 2018 *)

a(7)-a(34) from Michel Marcus, Jul 16 2018

A292559 Composite numbers m such that lpf(2^m - 1) == 1 (mod m).

Original entry on oeis.org

169, 221, 323, 611, 779, 793, 923, 1121, 1159, 1271, 1273, 1343, 1349, 1513, 1717, 1829, 1919, 2033, 2077, 2201, 2413, 2533, 2603, 2759, 2951, 3097, 3131, 3173, 3193, 3281, 3379, 3599, 3721, 3743, 3791, 3937, 3953, 4043, 4223, 4309, 4331, 4369, 4607, 4619, 4811, 4867, 4883, 4981, 5111, 5177, 5263, 5429, 5567, 5699

Offset: 1

Michel Marcus and Thomas Ordowski, Sep 19 2017

All terms are coprime to 2, 3, 5, 7, 11. - Robert Israel, Sep 20 2017
If p = lpf(2^m - 1) and A002326((p-1)/2) = m composite, then m is in this sequence. - Thomas Ordowski, Sep 20 2017
Conjecture: there are no numbers k in this sequence such that, for each prime factor q of 2^k - 1, q == 1 (mod k). - Thomas Ordowski, Sep 20 2017
Note: if all prime factors q of 2^k - 1 are q == 1 (mod k), then 2^k - 1 == 1 (mod k), thus 2^k == 2 (mod k), so k is a pseudoprime. The pseudoprime k = a(42) = 4369 = 17*257 is not a counterexample to this conjecture. A pseudoprime k = P*Q such that both 2^P - 1 and 2^Q - 1 are primes would be a counterexample, but the known Mersenne primes do not give such k. - Thomas Ordowski, Oct 02 2017
If lpf(2^n - 1) == 1 (mod n), then gpf(2^n - 1) == 1 (mod n). Cf. A291855. - Thomas Ordowski, Oct 20 2017
Composites m such that lpf(2^m - 1)*gpf(2^m - 1) is a Fermat pseudoprime to base 2, i.e., is in A214305. - Thomas Ordowski, Oct 29 2017

Subsequence of A236769.

Cf. A002326, A049479, A292834, A298076.

searchMax = 1000; Complement[Select[Range[searchMax], Mod[FactorInteger[2^# - 1][[1, 1]], #] == 1 &], Prime[Range[PrimePi[searchMax]]]] (* Alonso del Arte, Sep 19 2017 *)

lista(nn) = forcomposite(n=1, nn, sp = factor(2^n-1)[1,1]; if ((sp % n) == 1, print1(n, ", "))); \\ Michel Marcus, Sep 19 2017

A049479(m) == 1 (mod m).

a(10)-a(54) from Charles R Greathouse IV, Sep 19 2017

A215150 Pseudoprimes divisible by a smaller pseudoprime.

Original entry on oeis.org

13981, 18705, 23001, 55245, 63973, 72885, 75361, 107185, 126217, 129921, 137149, 157641, 158369, 172081, 176149, 188461, 215265, 266305, 272251, 276013, 278545, 285541, 294409, 348161, 387731, 423793, 464185, 488881, 493697, 617093, 625921, 743665, 748657, 825265

Offset: 1

Arkadiusz Wesolowski, Aug 04 2012

nonn

Here pseudoprime means a Fermat base-2 pseudoprime (a member of A001567).
Pseudoprimes by which the numbers from sequence are divisible: 341, 645, 561, 1905, 1729, 645, 341, 1105, 1387 and 1729, 341, 2047, 561, 5461, 2821, 1387, 1729, 1905, 1105, 2047, 1387, 2465 and 3277, 4681, 2701 and 4033 and 7957, 341, 5461, 4369, 5461, 2701, 4369, 5461, 10261, 1105, 1729, 1387 and 11305.
A pseudoprime can be divisible by more than one pseudoprime: e.g. 126217, 278545, 294409, 825265.

			Since 2^13980 = 1 mod 13981 and 13981 = 11 * 31 * 41, 13981 is a pseudoprime, and it is divisible by 341, a smaller pseudoprime. 13981 is therefore in the sequence.
The pseudoprimes 75361, 129921, 348161, etc., are also divisible by 341.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..1000
G. L. Honaker, Jr. and Chris Caldwell, Prime Curios! 13981
Eric Weisstein's World of Mathematics, Poulet Number
Index entries for sequences related to pseudoprimes

Cf. A001567, A214305.

lst1 = {}; lst2 = {}; r = 10^6; Do[If[! PrimeQ[n] && PowerMod[2, n - 1, n] == 1, AppendTo[lst1, n]], {n, 1, r, 2}]; l = Length[lst1]; Do[p = lst1[[a]]; b = 1; While[True, t = lst1[[b]]; If[p < 3*t, Break[]]; If[Divisible[p, t], AppendTo[lst2, p]; Break[]]; b++], {a, 2, l}]; lst2

A216667 Semiprime 2-pseudoprimes of the form 10k + 7.

Original entry on oeis.org

1387, 2047, 3277, 7957, 13747, 23377, 31417, 60787, 65077, 88357, 164737, 188057, 233017, 275887, 390937, 486737, 489997, 514447, 580337, 604117, 672487, 680627, 769567, 769757, 916327, 1092547, 1132657, 1145257, 1252697, 1293337, 1433407, 1493857, 1530787

Offset: 1

Marius Coman, Sep 13 2012

nonn

A very interesting observation due to Peter Bala: about half of the terms from the sequence have the form p*(4*p - 3), where p is prime. For this form of Fermat pseudoprimes see the sequences A213812 and A215343.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Poulet Number

Subsequence of A214305.

Cf. A001567.

list(lim)=my(v=List(),t); forprime(p=3,sqrtint(lim\=1), forprime(q=p+2,lim\p, t=p*q; if(t%10==7 && Mod(2,t)^t==2, listput(v,t)))); Set(v) \\ Charles R Greathouse IV, Jun 30 2017

A218483 Fermat pseudoprimes to base 2 which are congruent to 1 (mod 8).

Original entry on oeis.org

561, 1105, 1729, 1905, 2465, 4033, 4369, 4681, 6601, 8321, 8481, 10585, 11305, 12801, 15841, 16705, 18705, 18721, 23001, 23377, 25761, 30121, 30889, 31417, 31609, 33153, 34945, 39865, 41041, 41665, 46657, 52633, 62745, 65281, 74665, 75361, 83665, 85489

Offset: 1

Marius Coman, Oct 30 2012

nonn

Old name was: Fermat pseudoprimes to base 2 of the form 8*p*n + p^2, where p is prime and n natural.
For p = 5 the formula becomes 40*n + 25. From the first 15 pseudoprimes divisible by 5, 12 are of the form 40*n + 25 (beside 3 of them which are of the form 40*n + 5). Conjecture: there are no pseudoprimes to base 2 of the form 40*n + 15.
Note: it can be seen that a pseudoprime can be written in this formula in more than one way: e.g., 561 = 8*3*23 + 3^2 = 8*11*5 + 11^2 = 8*17*2 + 17^2 or 1905 = 8*3*79 + 3^2 = 8*5*47 + 5^2.
Conjecture: If a Fermat pseudoprime to base 2 can be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it can be written this way for any of its prime factors. Checked for all pseudoprimes from the sequence above.
Conjecture: If a Fermat pseudoprime to base 2 with two prime factors can be written as 8*p1*n + p1^2, where n is a natural number and p1 one of its two prime factors, then it can also be written as 8*p2*(-n) + p2^2, where p2 is the other prime factor. Checked for 4033 = 37*109(n = 9), 4369 = 17*257(n = 30), 4681 = 31*151(n = 15), 8321 = 53*157(n = 13), 18721 = 97*193(n = 12), 23377 = 97*241(n = 18), 31417 = 89*353(n = 33), 31609 = 73*433 (n = 45), 65281 = 97*673(n = 72), 85489 = 53*1613 (n = 195).
Conjecture: If a Fermat pseudoprime to base 2 cannot be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it cannot be written this way for any of its prime factors. Checked for the following pseudoprimes: 341, 645, 1387, 2047, 2701, 2821, 3277, 4371, 5461, 7957, 10261, 13741, 13747, 13981, 14491, 15709, 19951, 29341, 31621, 42799, 49141, 49981, 55245, 60701, 60787, 63973, 65077, 68101, 72885, 80581, 83333.
Note: from the first 72 pseudoprimes, 39 can be written this way.
All three conjectures are true (obvious from new characterization). - Charles R Greathouse IV, Dec 07 2014

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Eric Weisstein's World of Mathematics, Poulet Number.

Cf. A001567, A216023, A214305.

select(t -> 2 &^ t mod t = 2 and not isprime(t), [seq(1+8*j,j=0..10^5)]); # Robert Israel, Dec 07 2014

Select[8 * Range[10^4] + 1, PowerMod[2, # - 1, #] == 1 && CompositeQ[#] &] (* Amiram Eldar, Mar 30 2021 *)

is(n)=n%8==1 && Mod(2,n)^n==2 && !isprime(n) \\ Charles R Greathouse IV, Dec 07 2014

Corrected by Charles R Greathouse IV, Dec 07 2014

New name from Charles R Greathouse IV, Dec 07 2014

A291554 Primes q for which there exists a prime p < q such that 2^q == 2^p (mod pq).

Original entry on oeis.org

31, 73, 89, 109, 113, 127, 151, 157, 193, 233, 241, 257, 281, 307, 313, 331, 337, 353, 397, 433, 457, 499, 577, 593, 601, 641, 673, 683, 811, 919, 953, 1013, 1049, 1103, 1153, 1163, 1201, 1217, 1249, 1321, 1327, 1399, 1429, 1433, 1459, 1471, 1553, 1601, 1613, 1657, 1709, 1721, 1753, 1777, 1789, 1801, 1873, 1913, 1933, 1993

Offset: 1

Thomas Ordowski, Aug 26 2017

nonn

Largest prime divisors of pseudoprimes with two distinct prime factors.

All prime divisors of pseudoprimes with two prime factors are all primes except 2, 3, 5, 7, and 13.

			We have 2^31 == 2^11 == 2 (mod 11*31), so 31 is a term.
Note that 11*31 = 341 is a pseudoprime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A001567, A214305, A216838.

Select[Prime@ Range[300], Function[p, AnyTrue[Prime@ Range[PrimePi[p] - 1], Function[q, PowerMod[2, q, p q] == PowerMod[2, p, p q]]]]] (* Michael De Vlieger, Aug 27 2017 *)

is(n)=forprime(p=2,n-1, if(Mod(2,p*n)^gcd(n-1,p-1)==1, return(isprime(n)))); 0 \\ Charles R Greathouse IV, Aug 26 2017

is(n)=if(n<9 || !isprime(n), return(0)); my(t=Mod(1,znorder(Mod(2,n))), nm1=n-1); t=chinese(t, Mod(1,2)); forstep(p=lift(t),n-2,t.mod, if(isprime(p) && Mod(2,p*n)^gcd(nm1,p-1)==1, return(1))); 0 \\ Charles R Greathouse IV, Aug 31 2017

Equivalent congruences: 2^(pq) == 2 (mod pq), 2^q == 2^p == 2 (mod pq), 2^(q-p) == 1 (mod pq), 2^gcd(p-1,q-1) == 1 (mod pq).

More terms from Robert Israel, Aug 26 2017

A291617 Numbers p_1p_2...p_k such that (2^p_1-1)(2^p_2-1)...(2^p_k-1) is a Poulet number (A001567), where p_i are primes and k >= 2.

Original entry on oeis.org

230, 341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 14491, 15709, 18721, 19951, 23377, 31323, 31417, 31609, 31621, 35333, 38193, 42799, 49141, 49981, 60701, 60787, 65077, 65281, 80581, 83333, 85489

Offset: 1

Max Alekseyev and Thomas Ordowski, Aug 28 2017

nonn

Rotkiewicz (1965) proved that (2^p-1)*(2^q-1) is a Poulet number if and only if p*q is a Poulet number, where p,q are distinct primes. It follows that this sequence contains all nonsquare terms in A214305.
Generally, the sequence includes all squarefree super-Poulet numbers.
The terms n = 230, 31323, 38193, ... are not in A050217. Are there infinitely many such terms?

			The number n = 341 = 11*31 is a term, because m = (2^11-1)*(2^31-1) = 4395899025409 is a Poulet number.

Max Alekseyev, Table of n, a(n) for n = 1..66
A. Rotkiewicz, Sur les nombres pseudopremiers de la forme M_p M_q, Elemente der Mathematik 20 (1965): 108-109. (in French)

Cf. A001567, A050217, A214305.

Select[Select[Range[10^4], CompositeQ@ # && SquareFreeQ@ # &], ! PrimeQ[#] && PowerMod[2, (# - 1), #] == 1 &@ Apply[Times, Map[2^# - 1 &, FactorInteger[#][[All, 1]] ]] &] (* Michael De Vlieger, Aug 30 2017 *)

{ is_A291617(n) = my(p,m); if(isprime(n),return(0)); p=factor(n); m=prod(i=1,matsize(p)[1], (2^p[i,1]-1)^p[i,2]); Mod(2,m)^m==2; }

A321790 a(n) is the smallest base a > 2 such that a^(k-1) != 1 (mod k), where k = A001567(n), the n-th Fermat pseudoprime to base 2.

Original entry on oeis.org

3, 3, 3, 5, 3, 7, 3, 3, 5, 5, 7, 3, 3, 3, 3, 3, 3, 7, 3, 3, 3, 7, 3, 5, 3, 3, 3, 3, 3, 3, 3, 7, 3, 3, 5, 3, 3, 3, 3, 13, 3, 3, 3, 3, 5, 3, 3, 3, 3, 7, 3, 3, 13, 5, 3, 7, 3, 3, 3, 3, 3, 7, 3, 3, 3, 3, 3, 11, 3, 5, 5, 3, 3, 3, 5, 5, 3, 5, 7, 5, 5, 3, 13, 3, 3

Offset: 1

Thomas Ordowski, Nov 19 2018

nonn

a(n) <= A177415(n).
Each a(n) is an odd prime.
If k = A001567(n) is a Carmichael number, then a(n) = lpf(k).
Conjecture: if k = A001567(n) is semiprime, then a(n) < lpf(k).
The smallest numbers k = A001567(n) such that a(n) = prime(m) for m > 1 are 341, 1105, 1729, 75361, 29341, 162401, 334153, ... See A135720 > 561.
The smallest such semiprimes are 341, 2701, ?, 721801, ... Cf. A285549.

			The first Fermat pseudoprime to base 2 is 341, and 341 is not a Fermat pseudoprime to base 3, so a(1) = 3.

Cf. A001567, A002997, A083876, A135720, A177415, A214305, A285549.

A141710 is a subsequence.

a[p_] := Module[{m=3}, While[Mod[m^(p-1), p] == 1, m++]; m]; psp = Select[Range[3, 1000000, 2], CompositeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &]; Map[a, psp] (* Amiram Eldar, Nov 19 2018 *)

More terms from Amiram Eldar, Nov 19 2018

cp's OEIS Frontend

A300418 Number of semiprime Fermat pseudoprimes to base 2 (A214305) less than 10^n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A050217 Super-Poulet numbers: Poulet numbers whose divisors d all satisfy d|2^d-2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A316907 Numbers k such that 2^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A292559 Composite numbers m such that lpf(2^m - 1) == 1 (mod m).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A215150 Pseudoprimes divisible by a smaller pseudoprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A216667 Semiprime 2-pseudoprimes of the form 10k + 7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A218483 Fermat pseudoprimes to base 2 which are congruent to 1 (mod 8).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A291554 Primes q for which there exists a prime p < q such that 2^q == 2^p (mod pq).

Views

Author

Keywords

Comments

Examples

Links

A291617 Numbers p_1p_2...p_k such that (2^p_1-1)(2^p_2-1)...(2^p_k-1) is a Poulet number (A001567), where p_i are primes and k >= 2.