A086000 For p = prime(n), a(n) is the smallest N such that pN is a base-2 pseudoprime (that is, 2^(pN-1) = 1 mod pN).

187, 129, 247, 31, 85, 33, 73, 89, 85, 11, 73, 161, 15, 93, 157, 233, 481, 133, 281, 19, 391, 1067, 23, 193, 601, 307, 6361, 37, 29, 15, 2731, 545, 10213, 593, 31, 53, 2593, 499, 1205, 141155, 1261, 2281, 97, 3333, 1387, 1891, 1777, 3391, 381, 59, 20231, 97

Offset

2,1

Comments

Tables compiled by Pinch were used. Sequence A085999 lists a(n)*prime(n). It can be shown that a(n) has the form 1 + 2 ord(4, prime(n)) k for some k > 0, where the ord(x,y) function is the smallest positive integer r such that x^r = 1 mod y. The value of k for a(n) is given in sequence A086001. Note that prime(n) divides 2^a(n) - 2. Compare A085012, which gives the smallest prime q such that pq is a 2-pseudoprime.

Links

Amiram Eldar, Table of n, a(n) for n = 2..10001

R. G. E. Pinch, Pseudoprimes and their factors (FTP).

Eric Weisstein's World of Mathematics, Pseudoprime.

Example

a(2) = 187 because prime(2) = 3 and N=187 is the smallest number such that 3N is a 2-pseudoprime.

Mathematica

Table[p=Prime[n]; m=MultiplicativeOrder[4, p]; k=1; While[psp=p(1+2*m*k); PowerMod[2, psp-1, psp]!=1, k++ ]; 1+2*m*k, {n, 2, 100}]

Crossrefs

Cf. A001567 (base-2 pseudoprimes), A082654 (ord(4, p)), A085012, A085999, A086001.

Sequence in context: A068257 A226675 A226672 * A155544 A221974 A227869

Adjacent sequences: A085997 A085998 A085999 * A086001 A086002 A086003

Keyword

easy,nonn

Author

T. D. Noe, Jul 08 2003

Status

approved