A001262 -id:A001262 - cp's OEIS frontend

A140803 Numbers of the form (2^(pq)-1) /((2^p-1)(2^q-1)), where p>q are primes.

3, 11, 43, 151, 683, 2359, 2731, 43691, 174763, 599479, 2796203, 8727391, 9588151, 178956971, 715827883, 2454285751, 39268347319, 45812984491, 567767102431, 733007751851, 2932031007403, 10052678938039, 46912496118443, 145295143558111, 3002399751580331, 41175768098368951, 192153584101141163

Offset: 1

Vladimir Shevelev, Jul 15 2008, Jul 22 2008; corrected Sep 07 2008

nonn

The sequence contains, in particular, A126614 (q=2) and A143012 (q=3).

If pq-1 is squarefree then the terms of the sequence are either primes or overpseudoprimes to base 2 (see A141232). In particular, they are strong pseudoprimes to base 2 (A001262).

			Entry 3 from (q=2,p=3), entry 11 from (q=2,p=5), entry 43 from (q=2,p=7), entry 151 from (q=3,p=5), entry 683 from (q=2,p=11).

Robert Israel, Table of n, a(n) for n = 1..825
V. Shevelev, Process of "primoverization" of numbers of the form a^n-1, arXiv:0807.2332 [math.NT], 2008.
S. Wagstaff, Factorizations of 2^n-1

Cf. A001262, A141232, A126614, A143012.

N:= 100: # to use all (p,q) with p*q < N
Primes:= select(isprime,[$2..floor(N/2)]):
A:= {}:
for i from 1 to nops(Primes) do
  p:= Primes[i];
  Qs:= select(q -> q < N/p, [seq(Primes[j],j=1..i-1)]);
  A:= A union {seq((2^(p*q)-1)/(2^p-1)/(2^q-1),q=Qs)};
od:
A; # Robert Israel, Sep 02 2014

terms = 27; Clear[seq]; seq[m_] := seq[m] = Table[(2^(p q)-1)/((2^p-1) (2^q-1)), {q, Prime[Range[m]]}, {p, Prime[Range[PrimePi[q]+1, terms]]}] // Flatten // Union // PadRight[#, terms]&;
seq[1]; seq[m=2]; While[seq[m] != seq[m-1], m++]; seq[m] (* Jean-François Alcover, Sep 17 2018 *)

a(17) to a(27) from Robert Israel, Sep 03 2014

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Original entry on oeis.org

30, 320, 224, 240, 72, 360, 728, 0, 672, 216, 1320, 0, 0, 16, 5060, 60, 126, 10560, 216, 0, 3360, 2574, 150, 5040, 2808, 3600, 3600, 232, 400, 420, 22, 2700, 2784, 224, 96, 70, 1640, 240, 9200, 3600, 2760, 58344, 616, 504, 102, 5600, 8064, 264, 11880, 1440, 7488, 252

Offset: 1

Vladimir Shevelev, Jun 14 2008, Jul 13 2008

nonn

The zero terms are of a special interest. Indeed, since for any odd prime p, A137576((p-1)/2)=p, then it is natural to call "overpseudoprimes" those Poulet pseudoprimes A001567(n) for which a(n)=0.
Theorem. A squarefree composite number m = p_1*p_2*...*p_k is an overpseudoprime if and only if A002326((p_1-1)/2) = A002326((p_2-1)/2) = ... = A002326((p_k-1)/2). Moreover, every overpseudoprime is in A001262.
Note that in A001262 there exist terms which are not squarefree. The first is A001262(52) = 1194649 = 1093^2.
It can be shown that if an overpseudoprime is not a multiple of the square of a Wieferich prime (see A001220) then it is squarefree. Also all squares of Wieferich primes are overpseudoprimes.

Amiram Eldar, Table of n, a(n) for n = 1..10000
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arxiv:0806.3412 [math.NT], 2008-2012.

Cf. A137576, A001567, A001262, A002326, A006694.

fppQ[n_]:=PowerMod[2,n,n]==2;f[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; s={}; Do[If[fppQ[n] && CompositeQ[n],AppendTo[s,f[(n-1)/2 ]-n]],{n,1,10000}]; s (* Amiram Eldar, Dec 09 2018 after Jean-François Alcover at A137576 *)

f(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isfpp(n) = {Mod(2, n)^n==2 & !isprime(n) & n>1}; \\ A001567
lista(nn) = {for (n=1, nn, if (isfpp(n), print1(f((n-1)/2) - n, ", ");););} \\ Michel Marcus, Dec 09 2018

More terms via b137576.txt from R. J. Mathar, Jun 12 2010

More terms from Michel Marcus, Dec 09 2018

A230485 Strong pseudoprimes n to base 2 such that n-2 and n+2 are primes.

Original entry on oeis.org

3465253618401, 44202753561285411, 1640293473202755801, 10623546148468360251

Offset: 1

Shyam Sunder Gupta, Oct 20 2013

For all n, a(n)-2 is in A230810. - M. F. Hasler, Dec 08 2016

			3465253618401 is a strong pseudoprime (base 2) and 3465253618399 and 3465253618403 are primes.

Cf. A001567, A057942, A001262, A230483, A230484.

A230487 Strong pseudoprimes k to base 2 such that either k-2 or k+2 is prime.

Original entry on oeis.org

4681, 29341, 42799, 49141, 52633, 85489, 90751, 104653, 253241, 280601, 458989, 580337, 1004653, 1082401, 1207361, 1251949, 1302451, 1678541, 1907851, 1909001, 2419385, 2510569, 2811271, 3090091, 3539101, 5044033, 5049001, 5173601, 5489641, 5590621, 7177105

Offset: 1

Shyam Sunder Gupta, Oct 20 2013

nonn

			4681 is a strong pseudoprime (base 2) and 4679 is prime. 253241 is a strong pseudoprime (base 2) and 253243 is prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5001 from Shyam Sunder Gupta)

Union of A230483 and A230484.

Cf. A001567, A001262, A230485.

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Original entry on oeis.org

3277, 3281, 29341, 49141, 80581, 88357, 104653, 121463, 196093, 314821, 320167, 458989, 476971, 489997, 491209, 721801, 800605, 838861, 873181, 877099, 973241, 1004653, 1251949, 1268551, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1590751, 1678541, 1809697

Offset: 1

Thomas Ordowski, Apr 27 2019

nonn

As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.
Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.
It seems that, for defined pseudoprimes n (similar to the odd primes p),
b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.
Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.
Problem: are there infinitely many such numbers?

			2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...

Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 27 2019 *)

More terms from Amiram Eldar, Apr 27 2019

A020238 Strong pseudoprimes to base 12.

Original entry on oeis.org

91, 133, 145, 247, 1649, 1729, 2821, 8911, 9073, 10585, 13051, 13333, 16471, 19517, 20737, 21361, 24013, 24727, 26467, 29539, 31483, 31621, 34219, 34861, 35881, 38311, 38503, 40321, 53083, 67861, 79381, 79501, 88831, 97351, 115231, 121301, 131977

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..210 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A020140, A001262 (base 2), A020229 (base 3), A020230, A020231, A020232, A020233, A020234, A020235, A020236, A020237.

A020243 Strong pseudoprimes to base 17.

Original entry on oeis.org

9, 91, 145, 781, 1111, 2821, 4033, 4187, 5365, 5833, 6697, 7171, 15805, 19729, 21781, 22791, 24211, 26245, 31621, 33001, 33227, 34441, 35371, 38081, 42127, 49771, 71071, 74665, 77293, 78881, 88831, 96433, 97921, 98671, 101101, 102311, 125563, 129493

Offset: 1

David W. Wilson

nonn

R. J. Mathar, Table of n, a(n) for n = 1..748
Index entries for sequences related to pseudoprimes

Superset of A188755.

/* with A001262 */
isA020243(n)={ isStrongPsp(n,17) }
{ for(n=1,300000000,
        if(isA020243(n), print(n) ;) ;
) ;
} /* R. J. Mathar, Mar 07 2012 */

A020245 Strong pseudoprimes to base 19.

Original entry on oeis.org

9, 49, 169, 343, 1849, 2353, 2701, 4033, 4681, 6541, 6697, 7957, 9997, 12403, 13213, 13747, 15251, 16531, 18769, 19729, 24761, 30589, 31621, 31861, 32477, 41003, 49771, 63139, 64681, 65161, 66421, 68257, 73555, 96049, 102831, 118957, 129961, 137311

Offset: 1

David W. Wilson

nonn

R. J. Mathar, Table of n, a(n) for n = 1..752
Index entries for sequences related to pseudoprimes

/* with A001262 */
isA020245(n)={ isStrongPsp(n,19) }
{ for(n=1,300000000, if(isA020245(n), print(n) ;) ;) ;} /* R. J. Mathar, Mar 07 2012 */

A063847 Carmichael numbers which are also base-2 strong pseudoprimes.

Original entry on oeis.org

15841, 29341, 52633, 252601, 314821, 1909001, 3581761, 4335241, 5049001, 5310721, 5444489, 15247621, 29111881, 35703361, 36765901, 38624041, 53711113, 68154001, 99036001, 101649241, 104852881, 115039081, 133800661, 161035057, 172290241, 214852609, 238244041, 299736181

Offset: 1

Shyam Sunder Gupta, Aug 26 2001

nonn

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

Cf. A001262, A002997.

Corrected and extended by Daniel Suteu, Oct 01 2019

A139791 Numbers n for which 2n is a multiple of A002326(n), the multiplicative order of 2 mod 2n+1.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36, 39, 41, 44, 48, 50, 51, 53, 54, 56, 63, 65, 68, 69, 74, 75, 78, 81, 83, 86, 89, 90, 95, 96, 98, 99, 105, 111, 113, 114, 116, 119, 120, 125, 128, 131, 134, 135, 138, 140, 141, 146, 153, 155, 156, 158, 165, 168, 170

Offset: 1

Vladimir Shevelev, May 21 2008, May 24 2008

nonn

The sequence properly contains A005097. 170 is the first number which is not in A005097. One can prove that A002326(2^(2t-1)) = 4t. Thus if n=2^(2t-1), where, for any m>0, t=2^(m-1) then 2n is a multiple of A002326(n) while 2n+1 is a Fermat number which, as well known, is not always a prime.

The sequence is the union of A005097 and (A001567 - 1)/2. [Conjectured by Vladimir Shevelev, proved by Ray Chandler, May 26 2008]

Christopher Adler and Jean-Paul Allouche (2022), Finite self-similar sequences, permutation cycles, and music composition, Journal of Mathematics and the Arts, 16:3, 244-261, DOI: 10.1080/17513472.2022.2116745.

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

Cf. A002326, A005097, A001262, A001567, A137576.

Select[Range[160], Divisible[2#, MultiplicativeOrder[2, 2#+1]] &] (* Amiram Eldar, Jun 28 2019 *)

isok(n) = !(2*n % znorder(Mod(2, 2*n+1))); \\ Michel Marcus, Nov 02 2017

Data extended up to a(68) = 170 to clarify distinction from A005097 and essentially identical sequences A130290 and A102781, by M. F. Hasler, Dec 13 2019

cp's OEIS Frontend

A140803 Numbers of the form (2^(p*q)-1) /((2^p-1)*(2^q-1)), where p>q are primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A230485 Strong pseudoprimes n to base 2 such that n-2 and n+2 are primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

A230487 Strong pseudoprimes k to base 2 such that either k-2 or k+2 is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A020238 Strong pseudoprimes to base 12.

Views

Author

Keywords

Links

Crossrefs

A020243 Strong pseudoprimes to base 17.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A020245 Strong pseudoprimes to base 19.

Views

Author

Keywords

Links

Programs

PARI

A063847 Carmichael numbers which are also base-2 strong pseudoprimes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A139791 Numbers n for which 2n is a multiple of A002326(n), the multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

A140803 Numbers of the form (2^(pq)-1) /((2^p-1)(2^q-1)), where p>q are primes.