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

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more

Comments

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.

Examples

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

References

• 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).

Links

• 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

Crossrefs

Cf. A089105, A089825.

Formula

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

Extensions

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