A085014 For p = prime(n), a(n) is the number of primes q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq.

0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 1, 3, 2, 2, 4, 1, 2, 3, 5, 4, 3, 6, 4, 4, 6, 4, 5, 4, 6, 5, 4, 2, 5, 8, 7, 5, 6, 3, 3, 3, 4, 5, 4, 4, 5, 9, 8, 7, 8, 5, 8, 7, 8, 4, 6, 6, 7, 7, 9, 6, 11, 7, 8, 2, 7, 12, 8, 6, 8, 4, 5, 5, 6, 5, 11, 10, 9, 11, 5, 8, 9, 12, 9, 4, 7, 13, 8, 5

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.

Index entries for sequences related to pseudoprimes

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

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

Sequence in context: A212620 A194859 A194838 * A082074 A132283 A307081

Adjacent sequences: A085011 A085012 A085013 * A085015 A085016 A085017

Keyword

nonn

Author

T. D. Noe, Jun 28 2003

Status

approved