cp's OEIS Frontend

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

%I A141768 #29 Aug 22 2025 06:28:23
%S A141768 9,25,49,91,341,481,703,1541,1891,2701,5461,6533,8911,12403,18721,
%T A141768 29341,31621,38503,79003,88831,146611,188191,218791,269011,286903,
%U A141768 385003,497503,597871,736291,765703,954271,1024651,1056331,1152271,1314631,1869211,2741311
%N A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.
%C A141768 These numbers are the worst cases for the Rabin-Miller probable-prime test.
%C A141768 Alford, Granville, & Pomerance show that this sequence is infinite.
%C A141768 The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.
%H A141768 Charles R Greathouse IV, <a href="/A141768/b141768.txt">Table of n, a(n) for n = 1..5476</a>
%H A141768 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 A141768 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 A141768 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 A141768 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 A141768 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%e A141768 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 A141768 (PARI) star(n)={n--;n>>valuation(n,2)};
%o A141768 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 A141768 r=0;forstep(n=9,1e8,2,if(isprime(n),next);t=bases(n);if(t>r,r=t;print1(n",")))
%Y A141768 Cf. A014233, A071294, A194946.
%K A141768 nonn,changed
%O A141768 1,1
%A A141768 _Charles R Greathouse IV_, Sep 15 2008
%E A141768 Edited by _Charles R Greathouse IV_, Jul 23 2010