A085014 - OEIS

%I #22 Mar 27 2021 08:00:21

%S 0,0,0,1,0,1,1,2,1,3,2,1,3,2,2,4,1,2,3,5,4,3,6,4,4,6,4,5,4,6,5,4,2,5,

%T 8,7,5,6,3,3,3,4,5,4,4,5,9,8,7,8,5,8,7,8,4,6,6,7,7,9,6,11,7,8,2,7,12,

%U 8,6,8,4,5,5,6,5,11,10,9,11,5,8,9,12,9,4,7,13,8,5

%N For p = prime(n), a(n) is the number of primes q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq.

%C Using a construction in Erdős's paper, it can be shown that a(prime(n)) > 0, except for the primes 3, 5, 7 and 13. 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 A085012 gives the smallest prime q such that q*prime(n) is a pseudoprime.

%C Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.

%D Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

%H Amiram Eldar, <a href="/A085014/b085014.txt">Table of n, a(n) for n = 2..337</a>

%H 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 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 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%F a(n) < 0.7 * p, where p is the n-th prime. - _Charles R Greathouse IV_, Apr 12 2012

%e a(11) = 3 because prime(11) = 31 and 2^30-1 has 3 prime factors (11, 151, 331) that yield pseudoprimes when multiplied by 31.

%t Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; cnt=0; Do[If[PowerMod[2, p*q[[i]]-1, p*q[[i]]]==1, cnt++ ], {i, Length[q]}]; cnt, {n, 2, 50}]

%Y Cf. A001567 (base-2 pseudoprimes), A085012, A086019, A180471.

%K nonn

%O 2,8

%A _T. D. Noe_, Jun 28 2003