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,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

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

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

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

Sequence in context: A324684 A213070 A221432 * A086019 A040968 A040967

Adjacent sequences: A085009 A085010 A085011 * A085013 A085014 A085015

Keyword

nonn

Author

T. D. Noe, Jun 28 2003

Status

approved