A085012 For p = prime(n), a(n) is the smallest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

0, 0, 0, 31, 0, 257, 73, 89, 113, 11, 73, 61681, 127, 178481, 157, 233, 1321, 20857, 281, 19, 2731, 13367, 23, 193, 601, 307, 6361, 37, 29, 43, 2731, 953, 168749965921, 593, 31, 53, 2593, 499, 101653, 62020897, 54001, 2281, 97, 19707683773, 5347, 29191

Offset: 2

Author

T. D. Noe, Jun 28 2003

Keywords

• nonn

Comments

Using a construction in Erdős's paper, it can be shown that every odd prime except 3, 5, 7 and 13 is a factor of some 2-factor pseudoprime. Note that the cofactor q can be very large; for p=317, the smallest is 381364611866507317969. Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. The sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.

Examples

			a(11) = 11 because prime(11) = 31 and 11 is the smallest factor of 2^30-1 that yields a pseudoprime when multiplied by 31.
		

References

• Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Links

• Amiram Eldar, Table of n, a(n) for n = 2..619
• Amiram Eldar, Table of n, a(n) for n = 2..1000 with 2 missing terms (marked with value 0)
• Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
• D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A001567 (base-2 pseudoprimes), A085014, A086019, A180471.

Programs

Mathematica

Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; i=1; While[i<=Length[q] && (PowerMod[2, p*q[[i]]-1, p*q[[i]]]>1), i++ ]; If[i>Length[q], 0, q[[i]]], {n, 2, 56}]