A020229 -id:A020229 - cp's OEIS frontend

A072276 Strong pseudoprimes to bases 2 and 3.

1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429, 16879501, 25326001, 27509653, 27664033, 28527049, 54029741, 61832377, 66096253, 74927161, 80375707, 101649241

Offset: 1

Francois R. Grieu, Jul 09 2002

nonn

Composites that pass the Miller-Rabin test for bases 2 and 3. The intersection of A001262 (strong pseudoprimes to base 2) and A020229 (strong pseudoprimes to base 3).

The Washington Bomfim link references a table with all terms up to 2^64. Data from Jan Feitsma and William Galway, see link below, permitted an easy determination of these terms. I tested the Mathematica function PrimeQ[n] with those numbers to verify that it is correct for all n < 2^64. - Washington Bomfim, May 13 2012

Don Reble, Table of n, a(n) for n = 1..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
D. Bleichenbacher, Thesis and strong pseudoprimes to 2 and 3 up to 10^16
Washington Bomfim, Table of n, a(n) for n=1..1499371 [a large file]
Jan Feitsma and William Galway, Tables of pseudoprimes and related data
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, section 4.2.3, Miller-Rabin test.
Eric Weisstein's World of Mathematics, Rabin-Miller test
Index entries for sequences related to pseudoprimes

Cf. A001262, A006945, A014233, A020229.

nmax = 10^8; sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n - 1, 2]; d = (n - 1)/2^s; If[ PowerMod[b, d, n] == 1, Return[True], Do[ If[ PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0,  s-1}]]); A072276 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 2] && sppQ[n, 3] , Print[n]; AppendTo[ A072276, n]]]; A072276 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

A298756 Least strong pseudoprime to base n.

Original entry on oeis.org

2047, 121, 341, 781, 217, 25, 9, 91, 9, 133, 91, 85, 15, 1687, 15, 9, 25, 9, 21, 221, 21, 169, 25, 217, 9, 121, 9, 15, 49, 15, 25, 545, 33, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 481, 9, 65, 49, 25, 49, 25, 51, 9, 55, 9, 55, 25, 57, 15, 481, 15, 9, 529, 9, 33

Offset: 2

Amiram Eldar, Jan 26 2018

nonn

a(n)=9 if and only if n == 1 or 8 (mod 9). - Robert Israel, Mar 27 2018

Robert Israel, Table of n, a(n) for n = 2..10000
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

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

filter:= proc(n,b) local d,s,r;
  if isprime(n) then return false fi;
  s:= padic:-ordp(n-1,2);
  d:= (n-1)/2^s;
  if b &^ d mod n = 1 then return true fi;
  for r from 0 to s-1 do
    if b &^ (d*2^r) + 1 mod n = 0 then return true fi
  od;
false
end proc:
f:= proc(b) local n;
  for n from 9 by 2 do if filter(n,b) then return n fi od
end proc:
map(f, [$2..100]); # Robert Israel, Mar 27 2018

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := Module[{ans=False},s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, ans=True, Do[If[PowerMod[b, d*2^r, n] == n-1, ans=True], {r, 0, s-1}]];ans];leastSPP[b_] := Module[{k=3}, While[ !sppQ[k,b],k+=2];k]; Table[leastSPP[n],{n, 2, 100}] (* after Jean-François Alcover at A020229 *)

is_a001262(n, a)={ (bittest(n, 0) && !isprime(n) && n>8) || return; my(s=valuation(n-1, 2)); if(1==a=Mod(a, n)^(n>>s), return(1)); while(a!=-1 && s--, a=a^2); a==-1} \\ after M. F. Hasler in A001262
a(n) = forcomposite(c=1, , if(is_a001262(c, n), return(c))) \\ Felix Fröhlich, Mar 28 2018

A020237 Strong pseudoprimes to base 11.

Original entry on oeis.org

133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711, 23377, 43213, 43739, 47611, 48283, 49601, 50737, 50997, 56057, 58969, 68137, 74089, 85879, 86347, 87913, 88831, 102173, 111055, 114211, 115231, 137149, 139231, 171601, 172369, 193249, 196555

Offset: 1

David W. Wilson

nonn

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

Cf. A020139, A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A020236.

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

A141350 Overpseudoprimes to base 3.

Original entry on oeis.org

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

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 *)

A141390 Overpseudoprimes to base 5.

Original entry on oeis.org

781, 1541, 5461, 13021, 15751, 25351, 29539, 38081, 40501, 79381, 100651, 121463, 133141, 195313, 216457, 315121, 318551, 319507, 326929, 341531, 353827, 375601, 416641, 432821, 453331, 464881, 498451, 555397, 556421, 753667, 764941, 863329, 872101, 886411

Offset: 1

Vladimir Shevelev, Jun 29 2008

nonn

If h_5(n) is the multiplicative order of 5 modulo n, r_5(n) is the number of cyclotomic cosets of 5 modulo n then, by the definition, n is an overpseudoprime of base 5 if h_5(n)*r_5(n)+1=n. These numbers are in A020231. In particular, if n is squarefree such that its prime factorization is n=p_1*...*p_k, then n is overpseudoprime to base 5 iff h_5(p_1)=...=h_5(p_k). E.g., since h_5(101)=h_5(251)=h_5(401)=25, the number 101*251*401=10165751 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..327 (calculated from the b-file at A020231)
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, 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, A141350, A020231, A020229.

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

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

Inserted a(2) and a(8) and extended at the suggestion of Gilberto Garcia-Pulgarin by Vladimir Shevelev, Feb 06 2012

A215566 Strong pseudoprimes to bases 3 and 5.

Original entry on oeis.org

112141, 432821, 1024651, 1563151, 1627921, 3543121, 4291801, 5481451, 8595361, 9780409, 10679131, 11407441, 18790021, 21397381, 22369621, 25326001, 27012001, 32817151, 33796531, 35798491, 42149971, 48064021, 67680491, 99809051, 116151661, 118846151, 129762001

Offset: 1

M. F. Hasler, Aug 16 2012

nonn

Terms A215566[1,...,35] calculated from A020231[1,...,715] and double-checked (up to a(32)=178482151) using A020229[1,...,752].

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

Intersection of A020229 and A020231.

Cf. A072276, A215568.

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.

A140658 Overpseudoprimes to bases 2 and 3.

Original entry on oeis.org

5173601, 13694761, 16070429, 27509653, 54029741, 66096253, 102690677, 117987841, 193949641, 206304961, 314184487, 390612221, 393611653, 717653129, 960946321, 1157839381, 1236313501, 1481626513, 1860373241, 1921309633, 2217879901, 2412172153, 2626783921

Offset: 1

Vladimir Shevelev, Jul 10 2008

nonn

From the first 19 strong pseudoprimes to bases 2 and 3 (A072276) only 6 are overpseudoprimes to the same bases.

Daniel Suteu, Table of n, a(n) for n = 1..10000 (terms 1..105 from Amiram Eldar)
Index entries for sequences related to pseudoprimes

Intersection of A141232 and A141350; subsequence of A072276.

Cf. A001262, A020229.

More terms from Amiram Eldar, Jun 24 2019

A215565 Strong pseudoprimes to base 3 of the form 6*k-1.

Original entry on oeis.org

3281, 432821, 973241, 1551941, 1683683, 1898999, 2202257, 2545181, 2586083, 2795519, 3020093, 3028133, 4042403, 4099439, 4561481, 4923521, 5087171, 5173601, 5193161, 5774801, 6710177, 8243111, 9846401

Offset: 1

M. F. Hasler, Aug 16 2012

nonn

Motivated by the fact that most strong pseudoprimes to base 3 (A020229) are of the form 6*k+1.

Amiram Eldar, Table of n, a(n) for n = 1..2621 (calculated from the b-file at A020229)

Cf. A020229.

forstep(n=5,1e7,6,is_A020229(n) & print1(n","))

cp's OEIS Frontend

A072276 Strong pseudoprimes to bases 2 and 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A298756 Least strong pseudoprime to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A020237 Strong pseudoprimes to base 11.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A141350 Overpseudoprimes to base 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A141390 Overpseudoprimes to base 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A215566 Strong pseudoprimes to bases 3 and 5.

Views

Author

Keywords

Comments

Links

Crossrefs

A020238 Strong pseudoprimes to base 12.

Views

Author

Keywords

Links

Crossrefs

A140658 Overpseudoprimes to bases 2 and 3.

Views

Author

Keywords

Comments

Links

Crossrefs