OFFSET
2,4
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.
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
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.
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
T. D. Noe, Jun 28 2003
STATUS
approved