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

Author

T. D. Noe, Jul 08 2003

Keywords

• easy
• nonn

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.

Examples

			a(2) = 187 because prime(2) = 3 and N=187 is the smallest number such that 3N 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.

Crossrefs

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

Programs

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}]