Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(e) ISSN 0025-5718(p)

     

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: $\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:

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




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia