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
DOI: https://doi.org/10.1090/S0025-5718-05-01798-9
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?)

  • 1. A. Atkin and D. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73, 1023-1030, 2004.MR 2031423 (2004i:11147)
  • 2. E. Bach and R. Peralta, Asymptotic semismoothness probabilities, Math. Comp. 65, 1701-1715, 1996.MR 1370848 (98a:11123)
  • 3. D. Bernstein, Bounding smooth integers, ANTS-III proceedings, Lecture Notes in Compt. Sci. 1423, Springer, New York, 128-130, 1998. MR 1726065
  • 4. 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 0712964 (85j:11012)
  • 5. A. Y. Cheer and D. A. Goldston, A differential delay equation arising from the sieve of Eratosthenes, Math. Comp. 55, 129-141, 1990.MR 1023043 (90j:11091)
  • 6. 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 0046375 (13:724e)
  • 7. N. G. de Bruijn, The asymptotic behavior of a function occurring in the theory of primes, Journal of the Indian Mathematical Society (New Series) 15 (1951), 25-32. 50-60, 1951. MR 0043838 (13:326f)
  • 8. K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv För Matematik, Astromi Fysik. Band 22 A, no. 10, 1-14, 1930.
  • 9. A. Hildebrand, On the number of positive integers $ \leq$ x and free of prime factors $ >$ y, J. Number Theory 22, 289-307, 1986.MR 0831874 (87d:11066)
  • 10. A. Hildebrand, On the local behavior of $ \Psi(x,y)$ Trans. Amer. Math. Soc. 297, 729-751, 1986.MR 0854096 (87k:11099)
  • 11. A. Hildebrand and G. Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296, 265-290, 1986.MR 0837811 (87f:11066)
  • 12. A. Hildebrand and G. Tenenbaum, On integers without large prime factors, Journal de Théorie des Nombres de Bordeaux 5, 411-484, 1993.MR 1265913 (95d:11116)
  • 13. S. Hunter and J. Sorenson, Approximating the number of integers free of large prime factors, Math. Comp. 66, 1729-1741, 1997.MR 1423076 (98c:11093)
  • 14. G. Marsaglia, A. Zaman, and J. C. W. Marsaglia, Numerical solution of some classical differential-difference equations, Math. Comp. 53, 191-201, 1989. MR 0969490 (90h:65124)
  • 15. K. K. Norton, Numbers with small prime factors, and the least $ k$th power nonresidue, Mem. Amer. Math. Soc. 106, 9-27, 1971. MR 0286739 (44:3948)
  • 16. R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13, 242-247, 1938.
  • 17. 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 1850632 (2002e:11123)
  • 18. K. Suzuki, An estimate for the number of integers without large prime factors, Math. Comp., 73, 1013-1022, 2004.MR 2031422 (2005a:11142)

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: https://doi.org/10.1090/S0025-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

American Mathematical Society