|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|