login
A141768
Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.
10
9, 25, 49, 91, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8911, 12403, 18721, 29341, 31621, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631
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.
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