|
Search: id:A085012
|
|
|
| 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
5
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
2,4
|
|
|
COMMENT
|
Using a construction in Erdos' 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
|
P. Erdos, 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.
P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.
|
|
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 gives the largest prime q such that q*prime(n) is a pseudoprime.
Sequence in context: A159578 A140762 A028363 this_sequence A086019 A040968 A040967
Adjacent sequences: A085009 A085010 A085011 this_sequence A085013 A085014 A085015
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
T. D. Noe (noe(AT)sspectra.com), Jun 28 2003
|
|
|
Search completed in 0.002 seconds
|
