An estimate for the number of integers without large prime factors
HTML articles powered by AMS MathViewer
- by Koji Suzuki PDF
- Math. Comp. 73 (2004), 1013-1022 Request permission
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
- A. Atkin, and D. Bernstein, Prime sieves using binary quadratic forms, to appear in Mathematics of Computation.
- D. Bernstein, Bounding smooth integers, ANTS-III proceedings, Lecture Notes in Compt. Sci. 1423, Springer, New York, 128-130, 1998.
- E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
- C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
- 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.
- Adolf Hildebrand and Gérald Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296 (1986), no. 1, 265–290. MR 837811, DOI 10.1090/S0002-9947-1986-0837811-1
- Adolf Hildebrand, On the local behavior of $\Psi (x,y)$, Trans. Amer. Math. Soc. 297 (1986), no. 2, 729–751. MR 854096, DOI 10.1090/S0002-9947-1986-0854096-0
- Adolf Hildebrand and Gérald Tenenbaum, On integers free of large prime factors, Trans. Amer. Math. Soc. 296 (1986), no. 1, 265–290. MR 837811, DOI 10.1090/S0002-9947-1986-0837811-1
- Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411–484. MR 1265913
- Simon Hunter and Jonathan Sorenson, Approximating the number of integers free of large prime factors, Math. Comp. 66 (1997), no. 220, 1729–1741. MR 1423076, DOI 10.1090/S0025-5718-97-00874-0
- Karl K. Norton, Numbers with small prime factors, and the least $k$th power non-residue, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
- Paul Pritchard, A sublinear additive sieve for finding prime numbers, Comm. ACM 24 (1981), no. 1, 18–23. MR 600730, DOI 10.1145/358527.358540
- R. A. Rankin, The difference between consecutive prime numbers. V, Proc. Edinburgh Math. Soc. (2) 13 (1962/63), 331–332. MR 160767, DOI 10.1017/S0013091500025633
- Jonathan P. Sorenson, A fast algorithm for approximately counting smooth numbers, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 539–549. MR 1850632, DOI 10.1007/10722028_{3}6
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
- Received by editor(s): April 10, 2001
- Received by editor(s) in revised form: September 12, 2002
- Published electronically: July 1, 2003
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 1013-1022
- MSC (2000): Primary 11N25; Secondary 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-03-01571-0
- MathSciNet review: 2031422