A050217 -id:A050217 - cp's OEIS frontend

A291602 Composite integers k satisfying 2^d == 2^(k/d) (mod k) for all d|k and that are not Super-Poulet (A050217).

1105, 13981, 68101, 137149, 149281, 158369, 266305, 285541, 423793, 617093, 625921, 852841, 1052503, 1052929, 1104349, 1128121, 1306801, 1746289, 2940337, 3048841, 3828001, 4072729, 4154161, 4209661, 4682833, 6183601, 6236473, 6617929, 7803769, 9106141, 11157721, 11644921, 12096613, 12932989, 13554781

Offset: 1

Max Alekseyev, Aug 27 2017

nonn

The set difference of A291601 and A050217.

Terms that are Carmichael numbers (A002997) are given by A291612. - Altug Alkan, Aug 27 2017

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

Cf. A001567, A050217, A291601.

is(k) = {if(k == 1 || !(k%2) || isprime(k), return(0)); my(issp = 1); fordiv(k, d, if(Mod(2, d)^d != 2, issp = 0; break)); if(!issp, fordiv(k, d, if(d^2 <= k && Mod(2, k)^d != Mod(2, k)^(k/d), return(0))); 1, 0);} \\ Amiram Eldar, Apr 22 2024

A291612 Carmichael numbers k that satisfy 2^d == 2^(k/d) (mod k) for all d|k and are not Super-Poulet numbers (A050217).

Original entry on oeis.org

1105, 852841, 3828001, 17098369, 118901521, 150846961, 172947529, 186393481, 200753281, 686059921, 771043201, 1001152801, 1207252621, 1269295201, 1632785701, 1772267281, 2301745249, 4765950001, 4897161361, 5278692481, 6030849889, 8251854001, 12121569601, 12456671569

Offset: 1

Max Alekseyev, Thomas Ordowski, Altug Alkan, Aug 27 2017

nonn

Intersection of A002997 and A291602.

			Carmichael number 1105 = 5*13*17 is a term because 2^5 == 2^(13*17) (mod 1105), 2^13 == 2^(5*17) (mod 1105), 2^17 == 2^(5*13) (mod 1105) and it is not a Super-Poulet number.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (calculated using data from Claude Goutier; terms 1..2665 from Max Alekseyev)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Index entries for sequences related to Carmichael numbers.

Cf. A002997, A050217, A291602.

A074380 Sarrus numbers n (A001567) which satisfy mu(n) = -1 and which are not Super-Poulet numbers (A050217).

Original entry on oeis.org

561, 645, 1105, 1729, 1905, 2465, 2821, 4371, 6601, 8481, 8911, 10585, 12801, 13741, 13981, 15841, 16705, 25761, 29341, 30121, 30889, 33153, 34945, 41665, 46657, 52633, 57421, 68101, 74665, 83665, 87249, 88561, 91001, 93961, 113201

Offset: 1

Jani Melik, Sep 24 2002

nonn

Some of these are Carmichael numbers, A002997: 561, 1105, 1729, ....

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

Cf. A001567, A050217, A002997.

Select[ Range[115000], !PrimeQ[ # ] && OddQ[ # ] && PowerMod[2, # - 1, # ] == 1 && Union[ PowerMod[2, Drop[Divisors[ # ], 1], # ]] != {2} && MoebiusMu[ # ] != 1 &]

is(n)=if(isprime(n) || Mod(2,n)^(n-1)!=1 || moebius(n)>=0, return(0)); fordiv(n, d, if(Mod(2, d)^d!=2, return(1))); 0 \\ Charles R Greathouse IV, Sep 01 2016

Edited and extended by Robert G. Wilson v, Oct 03 2002

A291637 Carmichael numbers (A002997) that are super-Poulet numbers (A050217).

Original entry on oeis.org

294409, 1299963601, 4215885697, 4562359201, 7629221377, 13079177569, 19742849041, 45983665729, 65700513721, 147523256371, 168003672409, 227959335001, 459814831561, 582561482161, 1042789205881, 1297472175451, 1544001719761, 2718557844481, 3253891093249, 4116931056001, 4226818060921, 4406163138721, 4764162536641, 4790779641001, 5419967134849, 7298963852041, 8470346587201

Offset: 1

Max Alekseyev and Thomas Ordowski, Aug 28 2017

nonn

Problem: are there infinitely many such numbers?
From Daniel Suteu, Sep 17 2020: (Start)
If we consider f(n) to be the smallest number in the sequence with n prime factors, then we have:
f(3) = 294409,
f(4) = 3018694485093841,
f(5) <= 521635331852681575100906881,
f(6) <= 2835402730651853232634509813787097410561,
f(7) <= 165784025660216242122027716057592895796242004385542265601. (End)

Amiram Eldar, Table of n, a(n) for n = 1..5328 (calculated using data from Claude Goutier; terms 1..983 from Max Alekseyev)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Index entries for sequences related to Carmichael numbers.

Intersection of A178997 and A002997.

A328665 Least super-Poulet number (A050217) with n distinct prime factors.

Original entry on oeis.org

341, 294409, 9972894583, 1264022137981459, 14054662152215842621

Offset: 2

Amiram Eldar, Oct 24 2019

a(7) <= 1842158622953082708177091, and a(8) <= 317565023788749598474704753433331761 (from Michon's site).
From Daniel Suteu, Oct 28 2019: (Start)
a(8)  <= 192463418472849397730107809253922101,
a(9)  <= 1347320741392600160214289343906212762456021,
a(10) <= 70865138168006643427403953978871929070133095474701,
a(11) <= 3363391752747838578311772729701478698952546288306688208857,
a(12) <= 132153369641266990823936945628293401491197666138621036175881960329,
a(13) <= 9105096650335639994239038954861714246150666715328403635257215036295306537. (End)

Gérard P. Michon, Super-pseudoprimes to Base a, Numericana, 2005.
Eric Weisstein's World of Mathematics, Super-Poulet Numbers
Wikipedia, Super-Poulet number

Cf. A001567, A007011, A050217, A178997, A300327.

a[n_] := Module[{k=1}, While[PrimeNu[k] < n || PowerMod[2, k - 1, k] != 1 || Union @ PowerMod[2, Rest[Divisors[k]], k] != {2}, k++]; k]; Array[a, 3, 2]

isok(k, n) = if (omega(k) == n, fordiv(k, d, if(Mod(2, d)^d!=2, return(0))); return(1));
a(n) = my(k=4); while (!isok(k, n), k++); k; \\ Michel Marcus, Oct 28 2019

isupperbound(n,k) = my(f=factor(k)); omega(f) == n && Mod(2, k)^gcd(vector(#f~, i, f[i,1]-1)) == 1; \\ Daniel Suteu, Oct 28 2019

A137576 a(n) = A002326(n) * A006694(n) + 1.

Original entry on oeis.org

1, 3, 5, 7, 13, 11, 13, 17, 17, 19, 31, 23, 41, 55, 29, 31, 41, 61, 37, 49, 41, 43, 85, 47, 85, 57, 53, 81, 73, 59, 61, 73, 73, 67, 111, 71, 73, 141, 151, 79, 217, 83, 89, 113, 89, 109, 131, 145, 97, 211, 101, 103, 169, 107, 109, 145, 113, 221, 133, 193, 221, 141, 301, 127

Offset: 0

Vladimir Shevelev, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008

nonn

Composite numbers n for which a((n-1)/2)=n are called overpseudoprimes to base 2 (A141232).
Theorem. If p and q are odd primes then the equality a((pq-1)/2)=pq is valid if and only if A002326((p-1)/2)=A002326((q-1)/2). Example: A002326(11) = A002326(44). Since 23 and 89 are primes then a((23*89-1)/2)=23*89.
A generalization: If p_1A002326((p_1-1)/2)= A002326((p_2-1)/2)=...=A002326((p_m-1)/2).
Moreover, if n is an odd squarefree number and a((n-1)/2)=n then also all divisors d of n satisfy a((d-1)/2)=d and d divides 2^d-2. Thus the sequence of such n is a subsequence of A050217.

Ray Chandler, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, Exact exponent of remainder term of Gelfond's digit theorem in binary case, arXiv:0804.3682 [math.NT], 2008.
Vladimir Shevelev, Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithmetica 136 (2009), 91-100.

Cf. A002326, A006694, A138193, A138217, A138227, A141232, A195468.

a[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Dec 04 2015, adapted from PARI *)

a(n)=my(t);sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1 \\ Charles R Greathouse IV, Feb 20 2013

It can be shown that if p is an odd prime then a((p^k-1)/2)=1+k*phi(p^k).

a(n) = ord(2,2*n+1) * ((Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1) + 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Edited and extended by Ray Chandler, May 08 2008

A214305 Fermat pseudoprimes to base 2 with two prime factors.

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

A178997 Super-Poulet numbers having more than two different prime factors.

Original entry on oeis.org

294409, 1398101, 1549411, 1840357, 12599233, 13421773, 15162941, 15732721, 28717483, 29593159, 61377109, 66384121, 67763803, 74658629, 78526729, 90341197, 96916279, 109322501

Offset: 1

T. D. Noe, Jan 11 2011

nonn

This is a subsequence of the super-Poulet numbers, A050217. Of the first 1000 super-Poulet numbers, only 18 have more than two prime factors.
a(10000) = A001567(5287334), so about 0.19% of the pseudoprimes in that range are in this sequence. - Charles R Greathouse IV, Sep 16 2016
The smallest Super-Poulet number with three prime factors not all distinct is 5654273717 = 4733*1093^2, which is not in this sequence. - Emmanuel Vantieghem, Sep 25 2018

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
V. Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv preprint arXiv:1206:0606 [math.NT], 2012. - From _N. J. A. Sloane_, Oct 28 2012
V. Shevelev, G. García-Pulgarín, J. M. Velásquez-Soto and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.

okQ[n_] := CompositeQ[n] && PrimeNu[n] > 2 && AllTrue[Divisors[n], PowerMod[2, #, n] == 2&];
Reap[For[n = 1, n < 10^8, n = n+2, If[okQ[n], Print[n]; Sow[n]]]][[2, 1]] (* Jean-François Alcover, Sep 11 2018 *) (* Corrected with PrimeNu instead of PrimeOmega by Emmanuel Vantieghem, Sep 24 2018 *)

is(n)=my(f=factor(n)); if(#f~ < 3, return(0)); fordiv(f, d, if(Mod(2, d)^d!=2, return(0))); 1 \\ Charles R Greathouse IV, Sep 01 2016

A328662 Super pseudoprimes (or superpseudoprimes) to base 3: Fermat pseudoprimes to base 3 all of whose divisors that are larger than 1 are either primes or Fermat pseudoprimes to base 3.

Original entry on oeis.org

91, 121, 671, 703, 949, 1541, 1891, 2701, 3281, 7381, 8401, 12403, 14383, 15203, 16531, 18721, 23521, 24727, 28009, 30857, 31621, 31697, 38503, 44287, 46999, 47197, 49051, 49141, 55261, 55969, 63139, 72041, 74593, 79003, 82513, 83333, 88573, 88831, 90751, 96139

Offset: 1

Amiram Eldar, Oct 24 2019

nonn

The super pseudoprimes to base 2 are the super-Poulet numbers (A050217).
Includes all the semiprimes in A005935. The first terms that are not semiprimes are 7381, 512461, 532171, 1018601, ... (A328663).
Subsequence of A271116. - Bill McEachen, Nov 06 2020

			91 is in the sequence since it is a Fermat pseudoprime to base 3, and its proper divisors that are larger than 1 are the primes 7 and 13.
7381 is in the sequence since it is a Fermat pseudoprime to base 3, and its proper divisors that are larger than 1 are the primes 11 and 61, and the composite numbers 121 and 671 that are Fermat pseudoprimes to base 3.

Michal Krížek, Florian Luca, and Lawrence Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer-Verlag, New York, 2001, chapter 12, Fermat's Little Theorem, Pseudoprimes, and Superpseudoprimes, pp. 130-146.

Amiram Eldar, Table of n, a(n) for n = 1..10000
J. Fehér and P. Kiss, Note on super pseudoprime numbers, Ann. Univ. Sci. Budapest, Eötvös Sect. Math., Vol. 26 (1983), pp. 157-159, entire volume.
B. M. Phong, On super pseudoprimes which are products of three primes, Ann. Univ. Sci. Budapest. Eótvós Sect. Math., Vol. 30 (1987), pp. 125-129, entire volume.
Andrzej Rotkiewicz, Solved and unsolved problems on pseudoprime numbers and their generalizations, Applications of Fibonacci numbers, Springer, Dordrecht, 1999, pp. 293-306.
Lawrence Somer, On superpseudoprimes, Mathematica Slovaca, Vol. 54, No. 5 (2004), pp. 443-451.

Subsequence of A005935.

Cf. A050217.

aQ[n_]:=  CompositeQ[n] && AllTrue[Rest[Divisors[n]], PowerMod[3, #-1, #] == 1 &]; Select[Range[10^5], aQ]

A179839 Semiprimes p*q with p < q and 2^p (mod q) == 2^q (mod p).

Original entry on oeis.org

341, 731, 1333, 1387, 1727, 2047, 2701, 3277, 3503, 3763, 4033, 4369, 4681, 5461, 7957, 8321, 9509, 10261, 10669, 13747, 14491, 15709, 17557, 17861, 18721, 19147, 19951, 20737, 23377, 31417, 31609, 31621, 35333, 42799, 43921, 44669, 46979, 49141, 49901, 49981

Offset: 1

T. D. Noe, Jan 10 2011

nonn

The semiprime super-Poulet numbers (semiprimes in A050217) are a subsequence.

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

Cf. A006881, A179707 (which allows p = q).

aQ[n_] := Module[{f = FactorInteger[n]}, If[Length[f] == 2 && f[[1, 2]] == f[[2, 2]] == 1, p = f[[1, 1]]; q = f[[2, 1]], Return[False]]; PowerMod[2, p, q] == PowerMod[2, q, p]]; Select[Range[50000], aQ] (* Amiram Eldar, Oct 23 2019 *)
Take[Times@@@Select[Tuples[Prime[Range[350]],2],#[[1]]!=#[[2]]&&PowerMod[2,#[[1]],#[[2]]]==PowerMod[2,#[[2]],#[[1]]]&]//Union,40] (* Harvey P. Dale, Jun 06 2025 *)

cp's OEIS Frontend

A291602 Composite integers k satisfying 2^d == 2^(k/d) (mod k) for all d|k and that are not Super-Poulet (A050217).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A291612 Carmichael numbers k that satisfy 2^d == 2^(k/d) (mod k) for all d|k and are not Super-Poulet numbers (A050217).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A074380 Sarrus numbers n (A001567) which satisfy mu(n) = -1 and which are not Super-Poulet numbers (A050217).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A291637 Carmichael numbers (A002997) that are super-Poulet numbers (A050217).

Views

Author

Keywords

Comments

Links

Crossrefs

A328665 Least super-Poulet number (A050217) with n distinct prime factors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A137576 a(n) = A002326(n) * A006694(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A214305 Fermat pseudoprimes to base 2 with two prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A178997 Super-Poulet numbers having more than two different prime factors.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

A328662 Super pseudoprimes (or superpseudoprimes) to base 3: Fermat pseudoprimes to base 3 all of whose divisors that are larger than 1 are either primes or Fermat pseudoprimes to base 3.