A001262 -id:A001262 - cp's OEIS frontend

A141350 Overpseudoprimes to base 3.

121, 703, 3281, 8401, 12403, 31621, 44287, 47197, 55969, 74593, 79003, 88573, 97567, 105163, 112141, 211411, 221761, 226801, 228073, 293401, 313447, 320167, 328021, 340033, 359341, 432821, 443713, 453259, 478297, 497503, 504913, 679057, 709873, 801139, 867043, 894781, 973241, 1042417

Offset: 1

Vladimir Shevelev, Jun 27 2008, corrected Sep 07 2008

nonn

If h_3(n) is the multiplicative order of 3 modulo n, r_3(n) is the number of cyclotomic cosets of 3 modulo n then, by the definition, n is an overpseudoprime to base 3 if h_3(n)*r_3(n)+1=n. These numbers are in A020229.

In particular, if n is squarefree such that its prime factorization is n=p_1*...*p_k, then n is overpseudoprime of base 3 iff h_3(p_1)=...=h_3(p_k).

Amiram Eldar, Table of n, a(n) for n = 1..10798 (calculated using the b-file at A020229)
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arXiv:0806.3412 [math.NT], 2008-2012.
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. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.

Cf. A141232, A137576, A001262, A020229, A062117, A006694.

ops3Q[n_] := CompositeQ[n] && GCD[n, 3] == 1 && MultiplicativeOrder[3, n]*(DivisorSum[n, EulerPhi[#]/MultiplicativeOrder[3, #] &] - 1) + 1 == n; Select[Range[10^6], ops3Q] (* Amiram Eldar, Jun 24 2019 *)

isok(n) = (n!=1) && !isprime(n) && (gcd(n,3)==1) && (znorder(Mod(3,n)) * (sumdiv(n, d, eulerphi(d)/znorder(Mod(3, d))) - 1) + 1 == n); \\ Michel Marcus, Oct 25 2018

a(10)-a(38) from Gilberto Garcia-Pulgarin added by Vladimir Shevelev, Feb 06 2012

A180065 Smallest strong pseudoprime to base 2 with n prime factors.

Original entry on oeis.org

2047, 15841, 800605, 293609485, 10761055201, 5478598723585, 713808066913201, 90614118359482705, 5993318051893040401, 24325630440506854886701, 27146803388402594456683201, 4365221464536367089854499301, 2162223198751674481689868383601, 548097717006566233800428685318301

Offset: 2

Kevin Batista (kevin762401(AT)yahoo.com), Aug 09 2010

nonn

			800605 is the third term because 800605 = 5 * 13 * 109 * 113, more prime factors than smaller 2-strong pseudoprimes.

Daniel Suteu, Table of n, a(n) for n = 2..17
Index entries for sequences related to pseudoprimes

Cf. A007011, A001262.

strong_check(p, base, e, r) = my(tv=valuation(p-1, 2)); tv > e && Mod(base, p)^((p-1)>>(tv-e)) == r;
strong_fermat_psp(A, B, k, base) = A=max(A, vecprod(primes(k))); (f(m, l, lo, k, e, r) = my(list=List()); my(hi=sqrtnint(B\m, k)); if(lo > hi, return(list)); if(k==1, forstep(p=lift(1/Mod(m, l)), hi, l, if(isprimepower(p) && gcd(m*base, p) == 1 && strong_check(p, base, e, r), my(n=m*p); if(n >= A && (n-1) % znorder(Mod(base, p)) == 0, listput(list, n)))), forprime(p=lo, hi, base%p == 0 && next; strong_check(p, base, e, r) || next; my(z=znorder(Mod(base, p))); gcd(m,z) == 1 || next; my(q=p, v=m*p); while(v <= B, list=concat(list, f(v, lcm(l, z), p+1, k-1, e, r)); q *= p; Mod(base, q)^z == 1 || break; v *= p))); list); my(res=f(1, 1, 2, k, 0, 1)); for(v=0, logint(B, 2), res=concat(res, f(1, 1, 2, k, v, -1))); vecsort(Set(res));
a(n) = if(n < 2, return()); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=strong_fermat_psp(x, y, n, 2)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ Daniel Suteu, Mar 04 2023

a(6)-a(10) and editing from Charles R Greathouse IV, Aug 29 2010

a(11)-a(15) from Daniel Suteu, Sep 24 2022

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Original entry on oeis.org

2047, 42799, 90751, 256999, 271951, 476971, 514447, 741751, 877099, 916327, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 2205967, 2304167, 2748023, 2811271, 2953711, 2976487, 3090091, 3116107, 4469471, 4863127, 5016191

Offset: 1

José María Grau Ribas, Mar 21 2016

nonn

Composite k == 3 (mod 4) such that 2*(-4)^((k-3)/4) == -1 (mod k). - Robert Israel, Mar 21 2016
2*(-4)^((p-3)/4) == -1 (mod p) is satisfied by all primes p == 3 (mod 4), see A318908. - Jianing Song, Sep 05 2018
Numbers in A047713 that are congruent to 3 mod 4. Most terms are congruent to 7 mod 8. For terms congruent to 3 mod 8, see A244628. - Jianing Song, Sep 05 2018
Question: Is this a subsequence of A001262? I have verified that it contains all terms up to 2^64. - Joseph M. Shunia, Jul 02 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..111 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.
A244628 is a proper subsequence.
Cf. A001262, A006971, A270698, A318908.

select(t -> not isprime(t) and 1 + 2*(-4) &^ ((t-3)/4) mod t = 0, [seq(i, i=7..10^7, 4)]); # Robert Israel, Mar 21 2016

Select[3 + 4*Range[10000000], PrimeQ[#] == False && PowerMod[1 + I, #, #] == Mod[1 - I, #] &]

forstep(n=3, 10^7, 4, if(Mod(2, n)^((n-1)/2)==kronecker(2, n) && !isprime(n), print1(n, ", ")))

A020236 Strong pseudoprimes to base 10.

Original entry on oeis.org

9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139, 100001, 102173, 118301, 118957, 134863, 139231, 148417, 158497, 166499, 188191, 196651, 201917, 216001, 226273, 231337, 237169, 251251, 287809, 302177

Offset: 1

David W. Wilson

nonn

			From _Alonso del Arte_, Aug 10 2018: (Start)
9 is a strong pseudoprime to base 10. It's not enough to check that 10^8 = 1 mod 9. Since 8 = 1 * 2^3, we also need to verify that 10 = 1 mod 9 and 10^2 = 1 mod 9 as well. Since these are both equal to 1, we see that 9 is indeed a strong pseudoprime to base 10.
91 is also a strong pseudoprime to base 10. Besides checking that 10^90 = 1 mod 91, since 90 = 45 * 2, we also check that 10^45 = -1 mod 91; the -1 is enough to satisfy the definition of a strong pseudoprime.
99 is a Fermat pseudoprime to base 10 (see A005939) but it is not a strong pseudoprime to base 10. Although 10^98 = 1 mod 99, since 98 = 49 * 2, we have to check 10^49 mod 99, and there we find not -1 nor 1 but 10. Therefore 99 is not in this sequence. (End)

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

Cf. A005939, A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.

strongPseudoprimeQ[b_, n_] := Module[{rems = Table[PowerMod[b, (n - 1)/2^expo, n], {expo, 0, IntegerExponent[n - 1,2]}]}, (rems[[-1]] == 1 || MemberQ[rems, n - 1]) && PowerMod[b, n - 1, n] == 1]; max = 5000; Select[Complement[Range[2, max], Prime[Range[PrimePi[max]]]], strongPseudoprimeQ[10, #] &] (* Alonso del Arte, Aug 10 2018 *)

A122929 Multiplicative order of 2 mod A141232(n).

Original entry on oeis.org

11, 28, 36, 52, 48, 60, 52, 148, 76, 68, 51, 52, 29, 92, 156, 92, 29, 179, 166, 100, 44, 102, 239, 156, 50, 25, 51, 364, 224, 204, 244, 166, 66, 346, 194, 388, 618, 92, 388, 102, 660, 371, 388, 29, 772, 828, 239, 460, 55, 292, 431, 166, 882, 1060, 532, 155, 68

Offset: 1

Vladimir Shevelev, Jul 05 2008, Jul 12 2008, Jul 23 2008

nonn

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

Cf. A141232, A002326, A001262, A141216.

a137576(n)=my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1;
lista(nn) = {forcomposite(n=1, nn, if ((n % 2) && (a137576((n-1)/2) == n), print1(znorder(Mod(2, n)), ", ");););} \\ Michel Marcus, Feb 09 2015

More terms from Michel Marcus, Feb 09 2015

A215568 Strong pseudoprimes to base 2 and 5.

Original entry on oeis.org

1907851, 4181921, 4469471, 5256091, 9006401, 9863461, 14709241, 25326001, 40987201, 55729957, 58449847, 67194401, 94502701, 100618933, 109437751, 114305441, 133800661, 135969401, 147028001, 153928133, 161304001, 192857761, 196049701, 213035761, 226359547, 245950561

Offset: 1

M. F. Hasler, Aug 16 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..880 (terms below 10^12; terms 1..381 from M. F. Hasler)

Intersection of A001262 and A020231.

Cf. A072276, A215566.

A230483 Strong pseudoprimes (base 2) that become prime when two is subtracted.

Original entry on oeis.org

4681, 29341, 42799, 49141, 52633, 85489, 90751, 104653, 458989, 1004653, 1082401, 1251949, 1302451, 1907851, 2510569, 2811271, 3090091, 3539101, 5044033, 5049001, 5489641, 5590621, 7177105, 9069229, 9073513, 9567673, 9995671, 10323769, 11473885, 12263131

Offset: 1

Shyam Sunder Gupta, Oct 20 2013

nonn

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

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

Cf. A001567, A001262, A230484, A230485, A230487.

A230484 Strong pseudoprimes (base 2) that become prime when two is added.

Original entry on oeis.org

253241, 280601, 580337, 1207361, 1678541, 1909001, 2419385, 5173601, 16324001, 18073817, 22849481, 25080101, 43363601, 60155201, 67194401, 82870517, 85519337, 97924217, 100943201, 102004421, 104857391, 116090081, 128987429, 134696801, 135969401, 145348529

Offset: 1

Shyam Sunder Gupta, Oct 20 2013

nonn

			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)

Cf. A001262, A230483, A230485, A230487.

A020239 Strong pseudoprimes to base 13.

Original entry on oeis.org

85, 1099, 5149, 7107, 8911, 9637, 13019, 14491, 17803, 19757, 20881, 22177, 23521, 26521, 35371, 44173, 45629, 54097, 56033, 57205, 75241, 83333, 85285, 86347, 102719, 110309, 153401, 184339, 191959, 222529, 242845, 253021, 253927, 269861

Offset: 1

David W. Wilson

nonn

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

/* insert A001262 code here */
isA020239(n)={
        isStrongPsp(n,13)
}
{
for(n=1,10000000000, if(isA020239(n), print(n) ;) ;) ;
} /* R. J. Mathar, Mar 07 2012 */

A068216 a(n) is the smallest n-digit pseudoprime (to base 2).

Original entry on oeis.org

341, 1105, 10261, 101101, 1004653, 10004681, 100017223, 1001152801, 10000321321, 100004790097, 1000001376901, 10000130243671, 100000105970311, 1000000191735161, 10000006286491369, 100000010102756401, 1000000114865704261, 10000000494514450733

Offset: 3

Patrick De Geest and Shyam Sunder Gupta, Feb 21 2002

Cf. A001567, A067845, A001262, A062568, A062852.

One more term from Farideh Firoozbakht, Jan 10 2007
More terms from Jens Kruse Andersen, May 11 2008
Offset corrected by Arkadiusz Wesolowski, Dec 14 2011

cp's OEIS Frontend

A141350 Overpseudoprimes to base 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A180065 Smallest strong pseudoprime to base 2 with n prime factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A122929 Multiplicative order of 2 mod A141232(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A215568 Strong pseudoprimes to base 2 and 5.

Views

Author

Keywords

Links

Crossrefs

A230483 Strong pseudoprimes (base 2) that become prime when two is subtracted.

Views

Author

Keywords

Examples

Links

Crossrefs

A230484 Strong pseudoprimes (base 2) that become prime when two is added.

Views

Author

Keywords

Examples

Links

Crossrefs

A020239 Strong pseudoprimes to base 13.

Views

Author

Keywords

Links

Programs

PARI

A068216 a(n) is the smallest n-digit pseudoprime (to base 2).

Views