

A141768


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


9



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 RabinMiller probableprime test.
Alford, Granville, & Pomerance show that this sequence is infinite.
The sequence is unchanged whether one, both, or neither of 1 and n1 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. 116.
Shyam Narayanan, Improving the Speed and Accuracy of the MillerRabin Primality Test
Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the MillerRabin Theorem (2014)
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128138.
Index entries for sequences related to pseudoprimes


EXAMPLE

25 is a 1, 7, 18 and 24strong 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.
Sequence in context: A030156 A192775 A246331 * A176970 A110284 A109367
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



