Remote Access Mathematics of Computation
Green Open Access

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

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

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

American Mathematical Society