login
A181782
Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.
4
25, 49, 65, 85, 91, 121, 125, 133, 145, 169, 175, 185, 205, 217, 221, 231, 247, 259, 265, 289, 301, 305, 325, 341, 343, 361, 365, 377, 385, 403, 425, 427, 435, 445, 451, 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
OFFSET
1,1
LINKS
EXAMPLE
49 is a strong pseudoprime to the bases 18, 19, 30 and 31, so 49 is in the sequence.
PROG
(PARI) /* function sppq() from http://www.jjj.de/pari/rabinmiller.gpi */
sppq(n, a)=
{ /* Return whether n is a strong pseudoprime to base a (Rabin Miller) */
local(q, t, b, e);
q = n-1; t = 0; while ( 0==bitand(q, 1), q\=2; t+=1 );
/* here n==2^t*q+1 */
b = Mod(a, n)^q;
if ( 1==b, return(1) );
e = 1;
while ( e<t,
if( (b==1) || (b==n-1), break(); );
b *= b;
e++;
);
return( if ( b!=(n-1), 0, 1 ) );
}
forstep(n=3, 1000, 2, if(isprime(n), next()); for(a=2, n-2, if(sppq(n, a), print1(n, ", "); break())); );
/* Joerg Arndt, Dec 27 2010 */
(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
CROSSREFS
Cf. A141768.
Sequence in context: A091300 A112771 A278931 * A322121 A020146 A020244
KEYWORD
nonn
AUTHOR
Karsten Meyer, Nov 10 2010
EXTENSIONS
Definition corrected by Max Alekseyev, Nov 12 2010
Terms corrected by Joerg Arndt, Dec 27 2010
STATUS
approved