

A085014


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


5



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^(p1)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. 105112.


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. 623624.
D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347354.
Index entries for sequences related to pseudoprimes


FORMULA

a(n) < 0.7 * p, where p is the nth prime.  Charles R Greathouse IV, Apr 12 2012


EXAMPLE

a(11) = 3 because prime(11) = 31 and 2^301 has 3 prime factors (11, 151, 331) that yield pseudoprimes when multiplied by 31.


MATHEMATICA

Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p1)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 (base2 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



