|
An estimate for the number of integers without large prime factors
Author(s):
Koji
Suzuki.
Journal:
Math. Comp.
73
(2004),
1013-1022.
MSC (2000):
Primary 11N25;
Secondary 11Y05
Posted:
July 1, 2003
MathSciNet review:
2031422
Retrieve article in:
PDF
This article is available free of charge
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.
References:
- 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
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
Email:
kohji.suzuki@fujixerox.co.jp
DOI:
10.1090/S0025-5718-03-01571-0
PII:
S 0025-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
Posted:
July 1, 2003
Copyright of article:
Copyright
2003,
American Mathematical Society
|