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

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?)

  • 1. A. Atkin, and D. Bernstein, Prime sieves using binary quadratic forms, to appear in Mathematics of Computation.
  • 2. D. Bernstein, Bounding smooth integers, ANTS-III proceedings, Lecture Notes in Compt. Sci. 1423, Springer, New York, 128-130, 1998.
  • 3. E. R. Canfield, P. Erdös, and C. Pomerance, On a problem of Oppenheim concerning ``factorisatio numerorum,'' J. Number Theory 17, 1-28, 1983. MR 85j:11012
  • 4. N. G. de Bruijn, On the number of positive integers $\leq$ x and free of prime factors $>$ y, Nederl. Akad. Wetensch. Proc. Ser. A54, 50-60, 1951. MR 13:724e
  • 5. K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv för Matematik, Astromi Fysik. Band 22 A, n:o 10, 1-14, 1930.
  • 6. A. Hildebrand, On the number of positive integers $\leq$ x and free of prime factors $>$ y, J. Number Theory 22, 289-307, 1986. MR 87f:11066
  • 7. A. Hildebrand, On the local behavior of $\Psi(x,y)$, Trans. Amer. Math. Soc. 297, 729-751, 1986. MR 87k:11099
  • 8. A. Hildebrand and G. Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296, 265-290, 1986. MR 87f:11066
  • 9. A. Hildebrand and G. Tenenbaum, On integers without large prime factors, Journal de Théorie des Nombres de Bordeaux 5, 411-484, 1993. MR 95d:11116
  • 10. S. Hunter and J. Sorenson, Approximating the number of integers free of large prime factors, Math. Comp. 66, 1729-1741, 1997. MR 98c:11093
  • 11. K. K. Norton, Numbers with small prime factors, and the least $k$th power nonresidue, Mem. Amer. Math. Soc. 106, 9-27, 1971. MR 44:3948
  • 12. P. Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24(1), 18-23, 772, 1981. MR 82c:10011
  • 13. R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13, 242-247, 1938. MR 28:3978
  • 14. J. P. Sorenson, A fast algorithm for approximately counting smooth numbers, ANTS-IV proceedings, Lecture Notes in Compt. Sci. 1838, Springer, New York, 539-549, 2000. MR 2002e:11123

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

American Mathematical Society