OFFSET
2,8
COMMENTS
Using a construction in Erdős's paper, it can be shown that a(prime(n)) > 0, except for the primes 3, 5, 7 and 13. 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 A085012 gives the smallest prime q such that q*prime(n) is a pseudoprime.
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..337
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.
FORMULA
a(n) < 0.7 * p, where p is the n-th prime. - Charles R Greathouse IV, Apr 12 2012
EXAMPLE
a(11) = 3 because prime(11) = 31 and 2^30-1 has 3 prime factors (11, 151, 331) that yield pseudoprimes when multiplied by 31.
MATHEMATICA
Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; cnt=0; Do[If[PowerMod[2, p*q[[i]]-1, p*q[[i]]]==1, cnt++ ], {i, Length[q]}]; cnt, {n, 2, 50}]
CROSSREFS
KEYWORD
nonn
AUTHOR
T. D. Noe, Jun 28 2003
STATUS
approved