login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A181782 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2. 4

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 5 18:15 EDT 2021. Contains 343572 sequences. (Running on oeis4.)