On the distribution of pseudoprimes
Author:
Carl Pomerance
Journal:
Math. Comp. 37 (1981), 587593
MSC:
Primary 10A21; Secondary 10A20
DOI:
https://doi.org/10.1090/S00255718198106287170
MathSciNet review:
628717
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: Let $\mathcal {P}(x)$ denote the pseudoprime counting function. With \[ L(x) = \exp \{ \log x\log \log \log x/\log \log x\} ,\] we prove $\mathcal {P}(x) \leqslant x \bullet L{(x)^{  1/2}}$ for large x, an improvement on the 1956 work of Erdös. We conjecture that $\mathcal {P}(x) = x \bullet L{(x)^{  1 + o(1)}}$.

N. G. de Bruijn, "On the number of positive integers $\leqslant x$ and free of prime factors $> y$. II," Nederl. Akad. Wetensch. Proc. Ser. A, v. 69, 1966, pp. 239247.
 E. Rodney Canfield and Carl Pomerance, On the problem of uniqueness for the maximum Stirling number(s) of the second kind, Integers 2 (2002), A1, 13. MR 1876176
 P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. MR 79031
 P. Erdős, On the sum $\sum _{d2^{n}1}d^{1}$, Israel J. Math. 9 (1971), 43–48. MR 269613, DOI https://doi.org/10.1007/BF02771618
 Carl Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), no. 1, 84–89. MR 581999, DOI https://doi.org/10.1112/S0025579300009967
 Carl Pomerance, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), no. 1, 4–9. MR 638549
 Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI https://doi.org/10.1090/S00255718198005728727 R. A. Rankin, "The difference between consecutive prime numbers," J. London Math. Soc., v. 13, 1938, pp. 242247.
Retrieve articles in Mathematics of Computation with MSC: 10A21, 10A20
Retrieve articles in all journals with MSC: 10A21, 10A20
Additional Information
Keywords:
Pseudoprime,
Carmichael number,
Euler’s function
Article copyright:
© Copyright 1981
American Mathematical Society