Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Approximating the number of integers free of large prime factors


Authors: Simon Hunter and Jonathan Sorenson
Journal: Math. Comp. 66 (1997), 1729-1741
MSC (1991): Primary 11N25, 11Y05; Secondary 11Y16
MathSciNet review: 1423076
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Define $\Psi (x,y)$ to be the number of positive integers $n\le x$ such that $n$ has no prime divisor larger than $y$. We present a simple algorithm that approximates $\Psi (x,y)$ in $O(y\{\frac {\log \log x}{\log y} + \frac 1{\log \log y}\})$ floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation $\Psi (x,y)\approx x\rho (\log x/\log y)$, where $\rho (u)$ is Dickman's function.


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


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11N25, 11Y05, 11Y16

Retrieve articles in all journals with MSC (1991): 11N25, 11Y05, 11Y16


Additional Information

Simon Hunter
Affiliation: Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208

Jonathan Sorenson
Affiliation: Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208
Email: sorenson@butler.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-97-00874-0
PII: S 0025-5718(97)00874-0
Keywords: Psixyology, integer factoring, analytic number theory, algorithmic number theory, computational number theory
Received by editor(s): December 1, 1994
Received by editor(s) in revised form: October 16, 1995, and August 21, 1996
Additional Notes: The first author was supported in part by a Butler Scholarship.
The second author was supported in part by NSF grant CCR-9204414.
Computing equipment was provided through a grant from the Holcomb Research Institute.
Article copyright: © Copyright 1997 American Mathematical Society