A050217 -id:A050217 - cp's OEIS frontend

A291601 Composite integers k such that 2^d == 2^(k/d) (mod k) for all d|k.

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

Offset: 1

Max Alekseyev, Aug 27 2017

nonn

Such k must be odd.
For d=1, we have 2^k == 2 (mod k), implying that k is a Fermat pseudoprime (A001567).
Every Super-Poulet number belongs to this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Robert Israel)

Subsequence of A001567.
Supersequence of A050217, their set difference is given by A291602.
Cf. A291602.

filter:= proc(n) local D,d;
  if isprime(n) then return false fi;
  D:= sort(convert(numtheory:-divisors(n),list));
  for d in D while d^2 < n do
    if 2 &^ d - 2 &^(n/d) mod n <> 0 then return false fi
  od:
  true
end proc:
select(filter, [seq(i,i=3..2*10^5,2)]); # Robert Israel, Aug 28 2017

filterQ[n_] := CompositeQ[n] && AllTrue[Divisors[n], PowerMod[2, #, n] == PowerMod[2, n/#, n]&];
Select[Range[1, 10^6, 2], filterQ] (* Jean-François Alcover, Jun 18 2020 *)

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

A333130 Numbers that are super pseudoprimes to both bases 2 and 3.

Original entry on oeis.org

2701, 18721, 31621, 49141, 83333, 90751, 104653, 226801, 282133, 653333, 665281, 721801, 873181, 1373653, 1530787, 1537381, 1584133, 1690501, 1755001, 1987021, 2008597, 2035153, 2284453, 2746589, 2944261, 3059101, 3116107, 3363121, 3375041, 3375487, 4082653, 4314967

Offset: 1

Amiram Eldar, Mar 08 2020

nonn

The first term that has more than 2 prime factors is a(1067) = A333131(1) = 11500521553.

The first term that is also a Carmichael number is a(1131) = 13079177569.

			2701 is a term since it is a Fermat pseudoprime to both bases 2 and 3, and its proper divisors that are larger than 1 are all primes: 37 and 73.

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

Intersection of A050217 and A328662.

Subsequence of A001567, A005935, A052155 and A153513.

pspQ[n_] := CompositeQ[n] && AllTrue[Rest @ Divisors[n], PowerMod[2, # - 1, #] == 1 && PowerMod[3, # - 1, #] == 1 &]; Select[Range[10^6], pspQ]

A333131 Super pseudoprimes to both bases 2 and 3 (A333130) with more than two prime factors (counted with multiplicity).

Original entry on oeis.org

11500521553, 13079177569, 52474339009, 168003672409, 229352039821, 280792563977, 318289021201, 428178002569, 918660756421, 2015841188197, 2367478228501, 2544457029601, 2639665216117, 3023595814801, 3457449931321, 3712164285421, 4348114583017, 6046196043229

Offset: 1

Amiram Eldar, Mar 08 2020

nonn

Up to 2^64 all the 1085 terms are nonsquarefree, 2 terms have 4 prime factors: a(163) = 18362297383286473 = 3037 * 6073 * 9109 * 109297 and a(651) = 2587580959818925201 = 18121 * 36241 * 54361 * 72481, and no term have more than 4 prime factors.

			11500521553 is a term since it is a Fermat pseudoprime to both bases 2 and 3, and its proper divisors that are larger than 1 are either primes (937, 1873, 6553) or Fermat pseudoprimes to both bases 2 and 3 (1755001, 6140161, 12273769, 11500521553).

Amiram Eldar, Table of n, a(n) for n = 1..1085 (terms below 2^64)

Subsequence of A001567, A005935, A050217, A052155, A153513, A178997, A328662, A328663, A333130.

pspQ[n_] := PrimeOmega[n] > 2 && AllTrue[Rest @ Divisors[n], PowerMod[2, # - 1, #] == 1 && PowerMod[3, # - 1, #] == 1 &]; seq = {}; Do[If[pspQ[n], AppendTo[seq, n]], {n, 1, 6*10^10}]; seq

A276733 Composite numbers n such that 2^lpf(n) == 2 (mod n), where lpf(n) = A020639(n).

Original entry on oeis.org

341, 1247, 1387, 2047, 2701, 3277, 3683, 4033, 4369, 4681, 5461, 5963, 7957, 8321, 9017, 9211, 10261, 13747, 14351, 14491, 15709, 17593, 18721, 19951, 20191, 23377, 24929, 25351, 29041, 31417, 31609, 31621, 33227, 35333, 37901, 42799, 45761, 46513, 49141, 49601, 49981

Offset: 1

Thomas Ordowski, Sep 16 2016

nonn

Super-Poulet numbers A050217 is a subsequence.
From Robert Israel, Sep 16 2016: (Start)
If p is a Wieferich prime (A001220), p^2 is in this sequence.
If p is a non-Wieferich prime, there are terms of the sequence divisible by p iff p < A006530(2^p-2). Is the latter true for all primes p except 2,3,5,7 and 13? (End)

Robert Israel, Table of n, a(n) for n = 1..1000

Cf. A006530, A020639, A050217.

filter:= n -> not isprime(n) and 2 &^ min(numtheory:-factorset(n)) - 2 mod n = 0:
select(filter, [seq(i,i=3..100000,2)]); # Robert Israel, Sep 16 2016

lista(nn) = forcomposite(n=2, nn, if (Mod(2, n)^factor(n)[1,1] == Mod(2, n), print1(n, ", "));); \\ Michel Marcus, Sep 16 2016

More terms from Michel Marcus, Sep 16 2016

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; }

A306487 Poulet numbers which are not super-Poulet numbers.

Original entry on oeis.org

561, 645, 1105, 1729, 1905, 2465, 2821, 4371, 6601, 8481, 8911, 10585, 11305, 12801, 13741, 13981, 15841, 16705, 18705, 23001, 25761, 29341, 30121, 30889, 33153, 34945, 39865, 41041, 41665, 46657, 52633, 55245, 57421, 62745, 63973, 68101, 72885, 74665, 75361

Offset: 1

Amiram Eldar, Feb 18 2019

nonn

Subsequence of A080747 from which this differs for the first time at n=78, with A080747(78) = 294409, a term not present here.
Is this sequence infinite?
According to Sierpinski there are infinitely many Poulet numbers which are not super-Poulet numbers. But his definition of Poulet numbers includes the even pseudoprimes to base 2 (A006935), and the proof is based on the infinitude of this sequence and that super-Poulet numbers are never even.

			561 is in the sequence because 2^561 % 561 == 2 but 33|561 and 2^33 % 33 = 8 <> 2. - _David A. Corneth_, Feb 28 2019

W. Sierpinski, Elementary Theory of Numbers, ed. A. Schinzel, North-Holland Mathematical Library (2nd ed.), Amsterdam: North Holland, 1988, Chapter V, p. 234, Exercise 1.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Poulet Number
Eric Weisstein's World of Mathematics, Super-Poulet Numbers
Wikipedia, Super-Poulet number

Cf. A001567, A050217, A006935, A080747.

Cf. A215672 (differs from a(13) = 11305 on, which is not in A215672).

Select[Select[Range[3, 100000, 2], !PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &], Union[PowerMod[2, Rest[Divisors[#]], #]] != {2}& ]

is_A001567(n) = {Mod(2, n)^(n-1)==1 && !isprime(n) && n>1}; \\ From A001567 by M. F. Hasler
is_A050217(n) = if(isprime(n), 0, fordiv(n, d, if(Mod(2, d)^d!=2, return(0))); (n>1)); \\ After Charles R Greathouse IV's Aug 27 2016 PARI-program in A050217.
is_A306487(n) = (is_A001567(n) && !is_A050217(n)); \\ (Probably could be reduced to a simpler program). - Antti Karttunen, Feb 28 2019

is(n) = {if(isprime(n) || n < 2 || n%2 == 0, return(0)); if(Mod(2, n)^n!=2, return(0) , d = divisors(n); for(i = 1, #d-1, if(Mod(2, d[i])^d[i]!=2, return(1) ) ) ); 0 } \\ David A. Corneth, Feb 28 2019

A337715 Numbers that are the product of two distinct odd numbers x*y such that 2^x (mod y) = 2^y (mod x) = 2.

Original entry on oeis.org

341, 525, 651, 765, 1155, 1387, 1683, 1935, 2047, 2701, 3277, 3751, 4033, 4165, 4305, 4369, 4455, 4681, 5461, 5525, 5715, 6025, 6643, 7161, 7239, 7957, 8265, 8321, 8925, 9471, 9605, 10261, 10571, 10965, 12103, 12325, 13113, 13747, 13981, 14491, 15709, 16275, 16485

Offset: 1

Bernard Schott, Sep 16 2020

nonn

Equivalently, terms of A176970 that are not square of odd primes. Every square of odd prime p^2 is a term of A176970, because by Fermat's little theorem, for p prime, then 2^p = 2 (mod p).

The super-Poulet numbers (A050217) form a subsequence with 341, 1387, 2047, 2701, ... (see example).

			For 341 = 11 * 31 that is a super-Poulet:
   2^11 (mod 31) = 2^31 (mod 11) = 2, hence 341 is a term;
For 525 = 3 * 5^2 * 7 = 15 * 35 = 21 * 25:
   2^15 (mod 35) = 2^35 (mod 15) = 8, but
   2^21 (mod 25) = 2^25 (mod 21) = 2, hence, 525 is a term.

Subsequence of A176970.

A050217 (super-Poulet) is a subsequence.

test := proc(n) local d, q; if n::odd then for d in NumberTheory:-Divisors(n)
do q := iquo(n, d); if q > d and 2 &^ d mod q = 2 and 2 &^ q mod d = 2 then return true fi od fi; false end: select(test, [$(1..10000)]); # Peter Luschny, Sep 17 2020

okQ[x_, y_] := PowerMod[2, x, y] == PowerMod[2, y, x] == 2 && !PrimeQ[Sqrt[x*y]];
nn = 20000;
Union[Reap[Do[If[x*y < nn && okQ[x, y], Sow[x*y]], {x, 1, nn/3, 2}, {y, x, nn/3, 2}]][[2, 1]]] (* Jean-François Alcover, Sep 29 2024, after Harvey P. Dale in A176970 *)

isok(n) = {if ((n % 2), fordiv(n, d, if ((d > n/d) && (lift(Mod(2, d)^(n/d)) == 2) && (lift(Mod(2, n/d)^d) == 2), return(1));););} \\ Michel Marcus, Sep 17 2020

More terms from Amiram Eldar, Sep 16 2020

A367228 Products of two consecutive Fermat numbers: a(n) = A000215(n) * A000215(n+1).

Original entry on oeis.org

15, 85, 4369, 16843009, 281479271743489, 79228162532711081671548469249, 6277101735386680764176071790128604879584176795969512275969

Offset: 0

Amiram Eldar, Nov 11 2023

a(7) has 116 digits and is too large to include in the data section.

Szymiczek (1966) proved that a(n) is a super-Poulet number (A050217) for all n >= 2. All the composite Fermat numbers (A281576) are also super-Poulet numbers.

Michal Krížek, Florian Luca and Lawrence Somer, 17 Lectures on Fermat Numbers, Springer-Verlag, N.Y., 2001, p. 142.

Amiram Eldar, Table of n, a(n) for n = 0..10
Andrzej Rotkiewicz, On pseudoprimes having special forms and a solution of K. Szymiczek's problem, Acta Mathematica Universitatis Ostraviensis, Vol. 13, No. 1 (2005), pp. 57-71.
Kazimierz Szymiczek, Note on Fermat numbers, Elemente der Mathematik, Vol. 21, No. 3 (1966), p. 59.

Cf. A000215, A050217, A281576.

f[n_] := 2^(2^n) + 1; a[n_] := f[n] * f[n + 1]; Array[a, 7, 0]

f(n) = 2^(2^n) + 1;
a(n) = f(n) * f(n+1);

a(n) = (2^(2^n) + 1) * (2^(2^(n+1)) + 1).

cp's OEIS Frontend

A291601 Composite integers k such that 2^d == 2^(k/d) (mod k) for all d|k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A333130 Numbers that are super pseudoprimes to both bases 2 and 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333131 Super pseudoprimes to both bases 2 and 3 (A333130) with more than two prime factors (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A276733 Composite numbers n such that 2^lpf(n) == 2 (mod n), where lpf(n) = A020639(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Extensions

A291617 Numbers p_1*p_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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A306487 Poulet numbers which are not super-Poulet numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A337715 Numbers that are the product of two distinct odd numbers x*y such that 2^x (mod y) = 2^y (mod x) = 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A367228 Products of two consecutive Fermat numbers: a(n) = A000215(n) * A000215(n+1).

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.