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,10

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 r<n. Sequence A086249 lists the number of pseudoprimes of order n.

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

Example

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

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<Length[d], i++ ]; num, {n, 100}]

Prog

(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 */

Crossrefs

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

Sequence in context: A084653 A354694 A143688 * A285549 A306310 A210454

Adjacent sequences: A086247 A086248 A086249 * A086251 A086252 A086253

Keyword

hard,nonn

Author

T. D. Noe, Jul 14 2003

Status

approved