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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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 November 23 16:15 EST 2014. Contains 249851 sequences.