The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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 Cf. A014233, A071294, A194946. Sequence in context: A192775 A318737 A246331 * A339126 A176970 A110284 Adjacent sequences: A141765 A141766 A141767 * A141769 A141770 A141771 KEYWORD nonn AUTHOR Charles R Greathouse IV Sep 15 2008 EXTENSIONS Edited by Charles R Greathouse IV, Jul 23 2010 STATUS approved

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

Last modified December 9 23:05 EST 2022. Contains 358710 sequences. (Running on oeis4.)