A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

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, 1869211, 2741311

Offset: 1

Author

Charles R Greathouse IV, Sep 15 2008

Keywords

• nonn
• changed

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.

Examples

			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.
		

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.
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A014233, A071294, A194946.

Programs

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",")))

Extensions

Edited by Charles R Greathouse IV, Jul 23 2010