cp's OEIS Frontend

A181782 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.

%I A181782 #38 Nov 21 2019 04:19:34
%S A181782 25,49,65,85,91,121,125,133,145,169,175,185,205,217,221,231,247,259,
%T A181782 265,289,301,305,325,341,343,361,365,377,385,403,425,427,435,445,451,
%U A181782 469,475,481,485,493,505,511,529,533,545,553,559,561,565,589,595,625,629,637,645,651,671,679,685,689,697
%N A181782 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.
%H A181782 Amiram Eldar, <a href="/A181782/b181782.txt">Table of n, a(n) for n = 1..10000</a>
%e A181782 49 is a strong pseudoprime to the bases 18, 19, 30 and 31, so 49 is in the sequence.
%o A181782 (PARI) /* function sppq() from http://www.jjj.de/pari/rabinmiller.gpi */
%o A181782 sppq(n,a)=
%o A181782 { /* Return whether n is a strong pseudoprime to base a (Rabin Miller) */
%o A181782     local(q, t, b, e);
%o A181782     q = n-1;  t = 0;  while ( 0==bitand(q,1), q\=2; t+=1 );
%o A181782     /* here  n==2^t*q+1 */
%o A181782     b = Mod(a, n)^q;
%o A181782     if ( 1==b, return(1) );
%o A181782     e = 1;
%o A181782     while ( e<t,
%o A181782         if( (b==1) || (b==n-1), break(); );
%o A181782         b *= b;
%o A181782         e++;
%o A181782     );
%o A181782     return( if ( b!=(n-1), 0, 1 ) );
%o A181782 }
%o A181782 forstep(n=3,1000,2,if(isprime(n),next());for(a=2,n-2,if(sppq(n,a),print1(n,", ");break())););
%o A181782 /* _Joerg Arndt_, Dec 27 2010 */
%o A181782 (PARI) select( is_A181782(n)={bittest(n,0) && !isprime(n) && for(a=2,n-2, my(t=valuation(n-1,2), b=Mod(a,n)^(n>>t)); b==1&&return(1); while(t-->0 && b!=-1 && b!=1, b=b^2); b==-1&&return(1))}, [1..700]) \\ Defines is_A181782(): select(...) gives a check and illustration for free. Inside the for loop is the exact equivalent of the sppq() function above. - _M. F. Hasler_, Nov 26 2018
%Y A181782 Cf. A141768.
%K A181782 nonn
%O A181782 1,1
%A A181782 _Karsten Meyer_, Nov 10 2010
%E A181782 Definition corrected by _Max Alekseyev_, Nov 12 2010
%E A181782 Terms corrected by _Joerg Arndt_, Dec 27 2010