Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Approximating the number of integers without large prime factors


Author: Koji Suzuki
Journal: Math. Comp. 75 (2006), 1015-1024
MSC (2000): Primary 11N25; Secondary 11Y05
Published electronically: December 2, 2005
MathSciNet review: 2199567
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: $ \Psi(x,y)$ denotes the number of positive integers $ \leq x$ and free of prime factors $ >y$. Hildebrand and Tenenbaum gave a smooth approximation formula for $ \Psi(x,y)$ in the range $ (\log x)^{1+\epsilon}< y \leq x$, where $ \epsilon$ is a fixed positive number $ \leq 1/2$. In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate $ \Psi(x,y)$. The computational complexity of this algorithm is $ O(\sqrt{(\log x)(\log y)})$. We give numerical results which show that this algorithm provides accurate estimates for $ \Psi(x,y)$ and is faster than conventional methods such as algorithms exploiting Dickman's function.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11N25, 11Y05

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


Additional Information

Koji Suzuki
Affiliation: Corporate Research Group, Fuji Xerox, 430, Sakai, Nakai-machi, Ashigarakami-gun, Kanagawa 259-0157, Japan
Email: kohji.suzuki@fujixerox.co.jp

DOI: http://dx.doi.org/10.1090/S0025-5718-05-01798-9
PII: S 0025-5718(05)01798-9
Keywords: Computational number theory, analytic number theory, asymptotic estimates, factoring problem
Received by editor(s): September 30, 2004
Received by editor(s) in revised form: December 13, 2004
Published electronically: December 2, 2005
Article copyright: © Copyright 2005 American Mathematical Society