A086019 For p = prime(n), a(n) is the largest 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, 683, 113, 331, 109, 61681, 5419, 2796203, 1613, 3033169, 1321, 599479, 122921, 38737, 22366891, 8831418697, 2931542417, 22253377, 268501, 131071, 28059810762433, 279073, 54410972897, 77158673929, 145295143558111

Offset

2,4

Comments

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. Sequence A085012 gives the smallest prime q such that 2^(pq-1) = 1 mod pq. Sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

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.

Example

a(9) = 683 because prime(9) = 23 and 683 is the largest factor of 2^22-1 that yields a pseudoprime when multiplied by 23.

Mathematica

Table[p=Prime[n]; q=Reverse[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, 40}]

Crossrefs

Cf. A001567 (base 2 pseudoprimes), A085012, A085014, A180471.

Sequence in context: A213070 A221432 A085012 * A040968 A040967 A040965

Adjacent sequences: A086016 A086017 A086018 * A086020 A086021 A086022

Keyword

hard,nonn

Author

T. D. Noe, Jul 08 2003

Status

approved