login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014233 Smallest odd number for which Miller-Rabin primality test on bases <= n-th 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. 58-61.

Zhenxiang Zhang and Min Tang, "Finding strong pseudoprimes to several bases. II", Mathematics of Computation 72 (2003), pp. 2085-2097.

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. 786-792

G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.

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, Miller-Rabin test.

C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.

Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355-380.

F. Raynal, Miller-Rabin's Primality Test

K. Reinhardt, Miller-Rabin Primality Test for odd n

Eric Weisstein's World of Mathematics, Strong Pseudoprime

Eric Weisstein's World of Mathematics, Rabin-Miller Strong Pseudoprime Test

Wikipedia, Miller-Rabin 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 19 23:11 EST 2014. Contains 252240 sequences.