|
%I #26 Jan 02 2018 00:44:13
%S 9,25,49,91,341,481,703,1541,1891,2701,5461,6533,8911,12403,18721,
%T 29341,31621,38503,79003,88831,146611,188191,218791,269011,286903,
%U 385003,497503,597871,736291,765703,954271,1024651,1056331,1152271,1314631
%N Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.
%C These numbers are the worst cases for the Rabin-Miller probable-prime test.
%C Alford, Granville, & Pomerance show that this sequence is infinite.
%C The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.
%H Charles R Greathouse IV, <a href="/A141768/b141768.txt">Table of n, a(n) for n = 1..5476</a>
%H W. R. Alford, A. Granville, and C. Pomerance (1994). "<a href="http://www.math.dartmouth.edu/~carlp/PDF/reliable.pdf">On the difficulty of finding reliable witnesses</a>". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
%H Shyam Narayanan, <a href="https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf">Improving the Speed and Accuracy of the Miller-Rabin Primality Test</a>
%H Shyam Narayanan, <a href="https://math.mit.edu/research/highschool/primes/materials/2014/conf/5-1-Narayanan.pdf">Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem</a> (2014)
%H Michael O. Rabin, <a href="http://dx.doi.org/10.1016/0022-314X(80)90084-0">Probabilistic algorithm for testing primality</a>, Journal of Number Theory 12:1 (1980), pp. 128-138.
%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%e 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.
%o (PARI) star(n)={n--;n>>valuation(n,2)};
%o 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])));
%o r=0;forstep(n=9,1e8,2,if(isprime(n),next);t=bases(n);if(t>r,r=t;print1(n",")))
%Y Cf. A014233, A071294, A194946.
%K nonn
%O 1,1
%A Charles R Greathouse IV Sep 15 2008
%E Edited by _Charles R Greathouse IV_, Jul 23 2010
|
