login
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.
6
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
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
KEYWORD
nonn
AUTHOR
T. D. Noe, Jun 28 2003
STATUS
approved