%I #38 Nov 21 2019 04:19:34
%S 25,49,65,85,91,121,125,133,145,169,175,185,205,217,221,231,247,259,
%T 265,289,301,305,325,341,343,361,365,377,385,403,425,427,435,445,451,
%U 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 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.
%H Amiram Eldar, <a href="/A181782/b181782.txt">Table of n, a(n) for n = 1..10000</a>
%e 49 is a strong pseudoprime to the bases 18, 19, 30 and 31, so 49 is in the sequence.
%o (PARI) /* function sppq() from http://www.jjj.de/pari/rabinmiller.gpi */
%o sppq(n,a)=
%o { /* Return whether n is a strong pseudoprime to base a (Rabin Miller) */
%o local(q, t, b, e);
%o q = n-1; t = 0; while ( 0==bitand(q,1), q\=2; t+=1 );
%o /* here n==2^t*q+1 */
%o b = Mod(a, n)^q;
%o if ( 1==b, return(1) );
%o e = 1;
%o while ( e<t,
%o if( (b==1) || (b==n-1), break(); );
%o b *= b;
%o e++;
%o );
%o return( if ( b!=(n-1), 0, 1 ) );
%o }
%o forstep(n=3,1000,2,if(isprime(n),next());for(a=2,n-2,if(sppq(n,a),print1(n,", ");break())););
%o /* _Joerg Arndt_, Dec 27 2010 */
%o (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 Cf. A141768.
%K nonn
%O 1,1
%A _Karsten Meyer_, Nov 10 2010
%E Definition corrected by _Max Alekseyev_, Nov 12 2010
%E Terms corrected by _Joerg Arndt_, Dec 27 2010
|