

A014233


Smallest odd number for which MillerRabin primality test on bases <= nth prime does not reveal compositeness.


3



2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Note that some terms are repeated.
Same as A006945 except for first term.
a(12) > 2^64. Hence the primality of numbers < 2^64 can be determined by asserting strong pseudoprimality to all prime bases <= 37 (=prime(12)). Testing to prime bases <=31 does not suffice, as a(11) < 2^64 and a(11) is a strong pseudoprime to all prime bases <= 31 (=prime(11)).  Joerg Arndt, Jul 04 2012


REFERENCES

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
S. Wagon, Primality testing, The Mathematical Intelligencer 8:3 (1986), pp. 5861.
Zhenxiang Zhang and Min Tang, "Finding strong pseudoprimes to several bases. II", Mathematics of Computation 72 (2003), pp. 20852097.


LINKS

Table of n, a(n) for n=1..11.
Index entries for sequences related to pseudoprimes
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786792
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915926.
Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see section 4.2.3, MillerRabin test.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 10031026.
Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355380.
F. Raynal, MillerRabin's Primality Test
K. Reinhardt, MillerRabin Primality Test for odd n
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Eric Weisstein's World of Mathematics, RabinMiller Strong Pseudoprime Test
Wikipedia, MillerRabin primality test


FORMULA

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


CROSSREFS

Sequence in context: A075950 A022527 A024009 * A160964 A022193 A069386
Adjacent sequences: A014230 A014231 A014232 * A014234 A014235 A014236


KEYWORD

nonn,hard,more


AUTHOR

Jud McCranie Feb 15 1997


EXTENSIONS

Minor edits from N. J. A. Sloane, Jun 20 2009
a(9)a(11) from Charles R Greathouse IV, Aug 14 2010


STATUS

approved



