cp's OEIS Frontend

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

%I A006945 M4673 #55 Apr 05 2025 10:27:31
%S A006945 9,2047,1373653,25326001,3215031751,2152302898747,3474749660383,
%T A006945 341550071728321,341550071728321,3825123056546413051,
%U A006945 3825123056546413051,3825123056546413051,318665857834031151167461,3317044064679887385961981
%N A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.
%C A006945 The tests are performed on sequential prime numbers starting with 2.  Note that some terms are repeated.
%C A006945 Same as A014233 except for the first term.
%D A006945 R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
%D A006945 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
%D A006945 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006945 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>
%H A006945 Eric Bach, <a href="https://doi.org/10.1090/S0025-5718-1990-1023756-8">Explicit bounds for primality testing and related problems</a>, Mathematics of Computation 55 (1990), pp. 355-380.
%H A006945 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 A006945 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 A006945 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 A006945 S. Wagon, <a href="http://dx.doi.org/10.1007/BF03025793">Primality testing</a>, Math. Intellig., 8 (No. 3, 1986), 58-61.
%H A006945 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 A006945 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%F A006945 Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). [_Charles R Greathouse IV_, May 17 2011]
%e A006945 2047=23*89. 1373653 = 829*1657. 25326001 = 11251*2251. 3215031751 = 151*751*28351. 2152302898747 = 6763*10627*29947.
%Y A006945 Cf. A089105, A089825.
%K A006945 nonn,hard,more
%O A006945 1,1
%A A006945 _N. J. A. Sloane_
%E A006945 Extended and description corrected by _Jud McCranie_ Feb 15 1997.
%E A006945 a(10)-a(12) from _Charles R Greathouse IV_, Aug 14 2010
%E A006945 a(13)-a(14) copied from A014233 by _Max Alekseyev_, Feb 15 2017