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

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

Amiram Eldar, Table of n, a(n) for n = 1..10000

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

Adjacent sequences: A181779 A181780 A181781 * A181783 A181784 A181785

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