This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006945 Smallest odd number that requires n Miller-Rabin primality tests.
(Formerly M4673)

%I M4673

%S 9,2047,1373653,25326001,3215031751,2152302898747,3474749660383,

%T 341550071728321,341550071728321,3825123056546413051,

%U 3825123056546413051,3825123056546413051,318665857834031151167461,3317044064679887385961981

%N Smallest odd number that requires n Miller-Rabin primality tests.

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

%C Same as A014233 except for the first term.

%D R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>

%H Eric Bach, <a href="http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/">Explicit bounds for primality testing and related problems</a>, Mathematics of Computation 55 (1990), pp. 355-380.

%H G. Jaeschke, <a href="http://dx.doi.org/10.1090/S0025-5718-1993-1192971-8">On strong pseudoprimes to several bases</a>, Math. Comp., 61 (1993), 915-926.

%H Yupeng Jiang, Yingpu Deng, <a href="http://arxiv.org/abs/1207.0063">Strong pseudoprimes to the first 9 prime bases</a>, arXiv:1207.0063v1 [math.NT], June 30, 2012.

%H C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1980-0572872-7">The pseudoprimes to 25.10^9</a>, Mathematics of Computation 35 (1980), pp. 1003-1026.

%H S. Wagon, <a href="http://dx.doi.org/10.1007/BF03025793">Primality testing</a>, Math. Intellig., 8 (No. 3, 1986), 58-61.

%H Zhenxiang Zhang and Min Tang, <a href="http://dx.doi.org/10.1090/S0025-5718-03-01545-X">Finding strong pseudoprimes to several bases. II</a>, Mathematics of Computation 72 (2003), pp. 2085-2097.

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

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

%Y Cf. A089105, A089825.

%K nonn,hard,more

%O 1,1

%A _N. J. A. Sloane_.

%E Extended and description corrected by _Jud McCranie_ Feb 15 1997.

%E a(10)-a(12) from _Charles R Greathouse IV_, Aug 14 2010

%E a(13)-a(14) copied from A014233 by _Max Alekseyev_, Feb 15 2017

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 19:54 EST 2019. Contains 320262 sequences. (Running on oeis4.)