OFFSET
1,1
COMMENTS
These numbers are the worst cases for the Rabin-Miller probable-prime test.
Alford, Granville, & Pomerance show that this sequence is infinite.
The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..5476
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
Shyam Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test
Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem (2014)
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128-138.
EXAMPLE
25 is a 1-, 7-, 18- and 24-strong pseudoprime and no odd number less than 25 has four or more bases to which it is a strong pseudoprime.
PROG
(PARI) star(n)={n--; n>>valuation(n, 2)};
bases(n)=my(f=factor(n)[, 1], nu=valuation(f[1]-1, 2), nn = star(n)); for(i=2, #f, nu = min(nu, valuation(f[i] - 1, 2)); ); (1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i])));
r=0; forstep(n=9, 1e8, 2, if(isprime(n), next); t=bases(n); if(t>r, r=t; print1(n", ")))
CROSSREFS
KEYWORD
nonn
AUTHOR
Charles R Greathouse IV Sep 15 2008
EXTENSIONS
Edited by Charles R Greathouse IV, Jul 23 2010
STATUS
approved