Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On the distribution of pseudoprimes


Author: Carl Pomerance
Journal: Math. Comp. 37 (1981), 587-593
MSC: Primary 10A21; Secondary 10A20
DOI: https://doi.org/10.1090/S0025-5718-1981-0628717-0
MathSciNet review: 628717
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \mathcal{P}(x)$ denote the pseudoprime counting function. With

$\displaystyle 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)}}$.

References [Enhancements On Off] (What's this?)

  • [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. 239-247.
  • [2] E. R. Canfield, P. Erdös & C. Pomerance, "On a problem of Oppenheim concerning "Factorisatio Numerorum"," J. Number Theory. (To appear.) MR 1876176 (2002j:11012)
  • [3] P. Erdös, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201-206. MR 0079031 (18:18e)
  • [4] P. Erdös, "On the sum $ {\Sigma _{d\vert{2^n} - 1}}\;{d^{ - 1}}$," Israel J. Math., v. 9, 1971, pp. 43-48. MR 0269613 (42:4508)
  • [5] C. Pomerance, "Popular values of Euler's function," Mathematika, v. 27, 1980, pp. 84-89. MR 581999 (81k:10076)
  • [6] C. Pomerance, "A new lower bound for the pseudoprime counting function," Illinois J. Math. (To appear.) MR 638549 (83h:10012)
  • [7] C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to $ 25\; \bullet \;{10^9}$," Math. Comp., v. 35, 1980, pp. 1003-1026. MR 572872 (82g:10030)
  • [8] R. A. Rankin, "The difference between consecutive prime numbers," J. London Math. Soc., v. 13, 1938, pp. 242-247.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A21, 10A20

Retrieve articles in all journals with MSC: 10A21, 10A20


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1981-0628717-0
Keywords: Pseudoprime, Carmichael number, Euler's function
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society