A086001 For p = prime(n), a(n) is the smallest k such that p*(1 + 2 Ord(4,p) k) is a base-2 pseudoprime.

93, 32, 41, 3, 7, 4, 4, 4, 3, 1, 2, 8, 1, 2, 3, 4, 8, 2, 4, 1, 5, 13, 1, 4, 6, 3, 60, 1, 1, 1, 21, 8, 74, 4, 1, 1, 16, 3, 7, 793, 7, 12, 1, 17, 7, 9, 24, 15, 5, 1, 85, 4, 1, 1, 4, 2155, 3, 1, 1, 25, 6, 1, 27, 1, 1669, 1, 1, 12, 6, 1, 4, 57, 15, 29, 817, 4, 2, 3, 4, 63, 3, 20, 1, 12, 3, 11, 3, 9, 31

Offset: 2

Author

T. D. Noe, Jul 08 2003

Keywords

• easy
• nonn

Comments

Sequences A085999 and A086000 list p*(1 + 2 Ord(4,p) k) and 1 + 2 Ord(4,p) k., respectively. Although, for any prime p, Dirichlet's theorem says the sequence 1 + 2 Ord(4,p) k contains an infinite number of primes, only a finite number of these produce a pseudoprime when multiplied by p.

Examples

			a(11) = 1 because prime(11) = 31, ord(4,31) = 5 and 31*(1+2*5*1) is a 2-pseudoprime.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 2..10001
• Eric Weisstein's World of Mathematics, Pseudoprime.

Crossrefs

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

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++ ]; k, {n, 2, 100}]