A086250 Smallest base-2 Fermat pseudoprime x that has ord(2,x) = n, or 0 if one does not exist.

0, 0, 0, 0, 0, 0, 0, 0, 0, 341, 2047, 0, 0, 5461, 4681, 4369, 0, 1387, 0, 13981, 42799, 15709, 8388607, 1105, 1082401, 22369621, 0, 645, 256999, 10261, 0, 16843009, 1227133513, 5726623061, 8727391, 1729, 137438953471, 91625968981, 647089, 561

Offset: 1

Author

T. D. Noe, Jul 14 2003

Keywords

• hard
• nonn

Comments

A base-2 Fermat pseudoprime is a composite number x such that 2^x == 2 (mod x). For such an x, ord(2,x) is the smallest positive integer m such that 2^m == 1 (mod x). For a number x to have order n, it must be a factor of 2^n-1 and not be a factor of 2^r-1 for rA086249 lists the number of pseudoprimes of order n.

Examples

			a(10) = 1 there is only 1 pseudoprime, 341 = 11*31, having order 10; that is, 2^10 = 1 mod 341.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 1..200
• R. G. E. Pinch, Pseudoprimes and their factors (FTP)
• Eric Weisstein's World of Mathematics, Pseudoprime

Crossrefs

Cf. A001567 (base-2 pseudoprimes), A086249.

Programs

Mathematica

Table[d=Divisors[2^n-1]; num=0; i=1; done=False; While[m=d[[i]]; done=!PrimeQ[m]&&PowerMod[2, m, m]==2&&MultiplicativeOrder[2, m]==n; If[done, num=m]; !done&&i
				

PARI

{ a(n) = fordiv(2^n-1,d, if(d>1 && (d-1)%n==0 && !ispseudoprime(d) && znorder(Mod(2,d))==n,return(d)) ); 0 } /* Max Alekseyev, Jan 07 2015 */