A020231 -id:A020231 - cp's OEIS frontend

A020236 Strong pseudoprimes to base 10.

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

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.

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.

A112450 Strong pseudoprimes (base-2) equal to product of 3 primes not necessarily distinct.

Original entry on oeis.org

15841, 29341, 52633, 74665, 252601, 314821, 476971, 635401, 1004653, 1023121, 1907851, 1909001, 2419385, 2953711, 3581761, 4335241, 4682833, 5049001, 5444489, 5599765, 5681809, 9069229, 13421773, 15247621, 15510041, 15603391, 17509501, 26254801, 26758057, 27966709

Offset: 1

Shyam Sunder Gupta, Dec 12 2005

nonn

The term a(11)=1907851 is also a strong pseudoprime to base 5, cf. A020231. M. F. Hasler, Aug 16 2012

			a(1) = 15841 = 7*31*73.

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

Intersection of A014612 and A001262.

More terms from Amiram Eldar, Nov 10 2019

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Original entry on oeis.org

15, 91, 703, 1891, 8911, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 5481451, 6186403, 6969511

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Odd numbers k such that A071294((k-1)/2) = A000010(k)/4.
For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.
The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.

			15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.

Amiram Eldar, Table of n, a(n) for n = 1..350
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.

Cf. A000010, A033181, A006945, A014233, A071294, A141768, A181782, A195328, A329468.

Cf. A001262, A020229, A020231, A020233.

o[n_] := (n - 1)/2^IntegerExponent[n - 1, 2];
a[n_?PrimeQ] := n - 1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2] & /@ (p - 1)]) - 1)/(2^om - 1))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]

A140509 Numbers k such that 5^k-1 contains a divisor which is an overpseudoprime to base 5.

Original entry on oeis.org

5, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80

Offset: 1

Vladimir Shevelev, Jun 30 2008

nonn

An odd prime p is in the sequence iff p is not in A004061.

Cf. A141390, A020231, A141232, A141350, A003463, A004061.

isokd(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); \\ A141390
isok(n) = {fordiv (5^n-1, dd, if (isokd(dd), return (1));); return (0);} \\ Michel Marcus, Oct 25 2018

Corrected and more terms from Michel Marcus, Oct 25 2018

A298757 Numbers k with record value of the least strong pseudoprime to base k (A298756).

Original entry on oeis.org

2, 1320, 4712, 5628, 7252, 7852, 14787, 17340, 61380, 78750, 254923, 486605, 1804842, 4095086, 12772344, 42162995

Offset: 1

Amiram Eldar, Jan 26 2018

The record strong pseudoprimes are 2047, 4097, 4711, 5627, 7251, 7851, 9409, 10261, 11359, 13747, 18299, 25761, 32761, 38323, 40501, 97921, ...

Index entries for sequences related to pseudoprimes

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

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]; smallestSPP[b_] := Module[ {k=3}, While[ !sppQ[k,b],k+=2];k ]; sm=0;a={};Do[s=smallestSPP[b];If[s>sm,sm=s;AppendTo[a,b]], {b,2,10^4}];a (* after Jean-François Alcover at A020229 *)

lista(nn) = {my(m=0); for (n=2, nn, my(r=a298756(n)); if (r>m, m =r; print1(n, ", ")););} \\ Michel Marcus, Jan 31 2022; using pari code in A298756

a(9)-a(16) from Jonathan Pappas, Jan 31 2022

cp's OEIS Frontend

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A215568 Strong pseudoprimes to base 2 and 5.

Views

Author

Keywords

Links

Crossrefs

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

A112450 Strong pseudoprimes (base-2) equal to product of 3 primes not necessarily distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A140509 Numbers k such that 5^k-1 contains a divisor which is an overpseudoprime to base 5.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A298757 Numbers k with record value of the least strong pseudoprime to base k (A298756).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions