cp's OEIS Frontend

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.

%I A085012 #21 Mar 27 2021 08:00:25
%S A085012 0,0,0,31,0,257,73,89,113,11,73,61681,127,178481,157,233,1321,20857,
%T A085012 281,19,2731,13367,23,193,601,307,6361,37,29,43,2731,953,168749965921,
%U A085012 593,31,53,2593,499,101653,62020897,54001,2281,97,19707683773,5347,29191
%N 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.
%C A085012 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.
%C A085012 Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.
%D A085012 Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.
%H A085012 Amiram Eldar, <a href="/A085012/b085012.txt">Table of n, a(n) for n = 2..619</a>
%H A085012 Amiram Eldar, <a href="/A085012/a085012.txt">Table of n, a(n) for n = 2..1000 with 2 missing terms (marked with value 0)</a>
%H A085012 Paul Erdős, <a href="http://www.jstor.org/stable/2304732">On the converse of Fermat's theorem</a>, Amer. Math. Monthly 56 (1949), p. 623-624.
%H A085012 D. H. Lehmer, <a href="http://www.jstor.org/stable/2301798">On the converse of Fermat's theorem</a>, Amer. Math. Monthly 43 (1936), p. 347-354.
%H A085012 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%e A085012 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.
%t A085012 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}]
%Y A085012 Cf. A001567 (base-2 pseudoprimes), A085014, A086019, A180471.
%K A085012 nonn
%O A085012 2,4
%A A085012 _T. D. Noe_, Jun 28 2003