A014233 -id:A014233 - cp's OEIS frontend

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

9, 25, 49, 91, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8911, 12403, 18721, 29341, 31621, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311

Offset: 1

Charles R Greathouse IV, Sep 15 2008

These numbers are the worst cases for the Rabin-Miller probable-prime test.
Alford, Granville, & Pomerance show that this sequence is infinite.
The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.

			25 is a 1-, 7-, 18- and 24-strong pseudoprime and no odd number less than 25 has four or more bases to which it is a strong pseudoprime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..5476
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
Shyam Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test
Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem (2014)
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128-138.
Index entries for sequences related to pseudoprimes

Cf. A014233, A071294, A194946.

star(n)={n--;n>>valuation(n,2)};
bases(n)=my(f=factor(n)[,1], nu=valuation(f[1]-1, 2), nn = star(n));for(i=2,#f,nu = min(nu, valuation(f[i] - 1, 2)););(1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i])));
r=0;forstep(n=9,1e8,2,if(isprime(n),next);t=bases(n);if(t>r,r=t;print1(n",")))

Edited by Charles R Greathouse IV, Jul 23 2010

A072276 Strong pseudoprimes to bases 2 and 3.

Original entry on oeis.org

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

A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.

Original entry on oeis.org

9, 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981

Offset: 1

N. J. A. Sloane

The tests are performed on sequential prime numbers starting with 2. Note that some terms are repeated.

Same as A014233 except for the first term.

			2047=23*89. 1373653 = 829*1657. 25326001 = 11251*2251. 3215031751 = 151*751*28351. 2152302898747 = 6763*10627*29947.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Matters Computational (The Fxtbook)
Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355-380.
G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp., 61 (1993), 915-926.
Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
S. Wagon, Primality testing, Math. Intellig., 8 (No. 3, 1986), 58-61.
Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Mathematics of Computation 72 (2003), pp. 2085-2097.
Index entries for sequences related to pseudoprimes

Cf. A089105, A089825.

Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). [Charles R Greathouse IV, May 17 2011]

Extended and description corrected by Jud McCranie Feb 15 1997.
a(10)-a(12) from Charles R Greathouse IV, Aug 14 2010
a(13)-a(14) copied from A014233 by Max Alekseyev, Feb 15 2017

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]

cp's OEIS Frontend

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A072276 Strong pseudoprimes to bases 2 and 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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