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

Author

Karsten Meyer, Nov 10 2010

Keywords

• nonn

Examples

			49 is a strong pseudoprime to the bases 18, 19, 30 and 31, so 49 is in the sequence.
		

Links

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

Crossrefs

Cf. A141768.

Programs

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 ( eJoerg 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

Extensions

Definition corrected by Max Alekseyev, Nov 12 2010

Terms corrected by Joerg Arndt, Dec 27 2010