Approximating the number of integers free of large prime factors
HTML articles powered by AMS MathViewer
- by Simon Hunter and Jonathan Sorenson PDF
- Math. Comp. 66 (1997), 1729-1741 Request permission
Abstract:
Define $\Psi (x,y)$ to be the number of positive integers $n\le x$ such that $n$ has no prime divisor larger than $y$. We present a simple algorithm that approximates $\Psi (x,y)$ in $O(y\{\frac {\log \log x}{\log y} + \frac 1{\log \log y}\})$ floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation $\Psi (x,y)\approx x\rho (\log x/\log y)$, where $\rho (u)$ is Dickman’s function.References
- D. J. Bernstein, Enumerating and counting smooth integers, Ch. 2, Ph.D. Thesis, University of California at Berkeley, May 1995.
- 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
- Adolf Hildebrand, On the number of positive integers $\leq x$ and free of prime factors $>y$, J. Number Theory 22 (1986), no. 3, 289–307. MR 831874, DOI 10.1016/0022-314X(86)90013-2
- 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, DOI 10.5802/jtnb.101
- N. A. Hmyrova, On polynomials with small prime divisors, Dokl. Akad. Nauk SSSR 155 (1964), 1268–1271 (Russian). MR 0160764
- N. A. Hmyrova, On polynomials with small prime divisors. II, Izv. Akad. Nauk SSSR Ser. Mat. 30 (1966), 1367–1372 (Russian). MR 0207660
- A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
- Pieter Moree, Psixyology and diophantine equations, Ph.D. thesis, Rijksuniversiteit Leiden, 1993.
- 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
- Carl Pomerance, Cryptology and computational number theory—an introduction, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 1–12. MR 1095548, DOI 10.1090/psapm/042/1095548
- Carl Pomerance, Factoring, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 27–47. MR 1095550, DOI 10.1090/psapm/042/1095550
- 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
- J. Sorenson, An introduction to prime number sieves, Tech. Report #909, Computer Sciences Department, University of Wisconsin-Madison, January 1990.
- N. M. Timofeev, Polynomials with small prime divisors, Taškent. Gos. Univ. Naučn. Trudy 548 Voprosy Mat. (1977), 87–91, 145 (Russian). MR 0565981
- J. van de Lune and E. Wattel, On the numerical solution of a differential-difference equation arising in analytic number theory, Math. Comp. 23 (1969), 417–421. MR 247789, DOI 10.1090/S0025-5718-1969-0247789-3
Additional Information
- Simon Hunter
- Affiliation: Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208
- Jonathan Sorenson
- Affiliation: Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208
- MR Author ID: 334195
- Email: sorenson@butler.edu
- Received by editor(s): December 1, 1994
- Received by editor(s) in revised form: October 16, 1995, and August 21, 1996
- Additional Notes: The first author was supported in part by a Butler Scholarship.
The second author was supported in part by NSF grant CCR-9204414.
Computing equipment was provided through a grant from the Holcomb Research Institute. - © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 1729-1741
- MSC (1991): Primary 11N25, 11Y05; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-97-00874-0
- MathSciNet review: 1423076