Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



An estimate for the number of integers without large prime factors

Author: Koji Suzuki
Journal: Math. Comp. 73 (2004), 1013-1022
MSC (2000): Primary 11N25; Secondary 11Y05
Published electronically: July 1, 2003
MathSciNet review: 2031422
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 provided a good approximation of $\Psi(x,y)$. However, their method requires the solution $\alpha=\alpha(x,y)$ to the equation $\sum_{p \leq y} \log p/(p^{\alpha} - 1) = \log x$, and therefore it needs a large amount of time for the numerical solution of the above equation for large $y$. Hildebrand also showed $1-\xi_u/\log y$ approximates $\alpha$ for $1 \leq u \leq y/(2 \log y)$, where $u=(\log x)/\log y$ and $\xi_u$ is the unique solution to $e^{\xi_u}=1+ u\xi_u$. Let $E(i)$ be defined by $E(0)=\log u; E(i)=\log u+\log ( E(i-1)+1/u )$ for $i>0$. We show $E(m)$ approximates $\xi_u$, and $1-E(m)/\log y$ also approximates $\alpha$, where $m=\lceil (\log u+\log \log y)/\log \log u \rceil+1$. Using these approximations, we give a simple method which approximates $\Psi(x,y)$ within a factor $1+O(1/u+1/\log y)$in the range $(\log \log x)^{5/3+\epsilon}<\log y<(\log x)/e$, where $\epsilon$ is any positive constant.

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: Information Media Laboratory, 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): April 10, 2001
Received by editor(s) in revised form: September 12, 2002
Published electronically: July 1, 2003
Article copyright: © Copyright 2003 American Mathematical Society