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

DOI:
https://doi.org/10.1090/S0025-5718-03-01571-0

Published electronically:
July 1, 2003

MathSciNet review:
2031422

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: denotes the number of positive integers and free of prime factors . Hildebrand and Tenenbaum provided a good approximation of . However, their method requires the solution to the equation , and therefore it needs a large amount of time for the numerical solution of the above equation for large . Hildebrand also showed approximates for , where and is the unique solution to . Let be defined by for . We show approximates , and also approximates , where . Using these approximations, we give a simple method which approximates within a factor in the range , where is any positive constant.

**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 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 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*, 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 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**

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

Email:
kohji.suzuki@fujixerox.co.jp

DOI:
https://doi.org/10.1090/S0025-5718-03-01571-0

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