login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes. 8
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.

REFERENCES

Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem, 2014; http://web.mit.edu/primes/materials/2014/conf/5-1-Narayanan.pdf

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.

Index entries for sequences related to pseudoprimes

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.

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

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

Content is available under The OEIS End-User License Agreement .

Last modified October 23 03:24 EDT 2014. Contains 248411 sequences.