Approximating the number of integers free of large prime factors

Authors:
Simon Hunter and Jonathan Sorenson

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Define to be the number of positive integers such that has no prime divisor larger than . We present a simple algorithm that approximates in 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 , where is Dickman's function.

**1.**D. J. Bernstein,*Enumerating and counting smooth integers*, Ch. 2, Ph.D. Thesis, University of California at Berkeley, May 1995.**2.**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**, https://doi.org/10.1016/0022-314X(83)90002-1**3.**N. G. de Bruijn,*The asymptotic behavior of a function occurring in the theory of primes*, Journal of the Indian Mathematical Society (New Series)**15**(1951), 25-32. MR**13:326f****4.**Adolf Hildebrand,*On the number of positive integers ≤𝑥 and free of prime factors >𝑦*, J. Number Theory**22**(1986), no. 3, 289–307. MR**831874**, https://doi.org/10.1016/0022-314X(86)90013-2**5.**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**, https://doi.org/10.1090/S0002-9947-1986-0837811-1**6.**Adolf Hildebrand and Gérald Tenenbaum,*Integers without large prime factors*, J. Théor. Nombres Bordeaux**5**(1993), no. 2, 411–484. MR**1265913****7.**N. A. Hmyrova,*On polynomials with small prime divisors*, Dokl. Akad. Nauk SSSR**155**(1964), 1268–1271 (Russian). MR**0160764****8.**N. A. Hmyrova,*On polynomials with small prime divisors. II*, Izv. Akad. Nauk SSSR Ser. Mat.**30**(1966), 1367–1372 (Russian). MR**0207660****9.**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****10.**Pieter Moree,*Psixyology and diophantine equations*, Ph.D. thesis, Rijksuniversiteit Leiden, 1993.**11.**Karl K. Norton,*Numbers with small prime factors, and the least 𝑘th power non-residue*, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR**0286739****12.**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**, https://doi.org/10.1090/psapm/042/1095548**13.**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**, https://doi.org/10.1090/psapm/042/1095550**14.**Paul Pritchard,*A sublinear additive sieve for finding prime numbers*, Comm. ACM**24**(1981), no. 1, 18–23. MR**600730**, https://doi.org/10.1145/358527.358540**15.**J. Sorenson,*An introduction to prime number sieves*, Tech. Report #909, Computer Sciences Department, University of Wisconsin-Madison, January 1990.**16.**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****17.**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**, https://doi.org/10.1090/S0025-5718-1969-0247789-3

Retrieve articles in *Mathematics of Computation*
with MSC (1991):
11N25,
11Y05,
11Y16

Retrieve articles in all journals with MSC (1991): 11N25, 11Y05, 11Y16

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

Email:
sorenson@butler.edu

DOI:
https://doi.org/10.1090/S0025-5718-97-00874-0

Keywords:
Psixyology,
integer factoring,
analytic number theory,
algorithmic number theory,
computational number theory

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.

Article copyright:
© Copyright 1997
American Mathematical Society