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

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, P. Erd\H{o}s, and C. Pomerance,*On a problem of Oppenheim concerning ``Factorisatio Numerorum''*, Journal of Number Theory**17**(1983), 1-28. MR**85j:11012****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.**A. Hildebrand,*On the number of positive integers and free of prime factors*, Journal of Number Theory**22**(1986), 289-307. MR**87d:11066****5.**A. Hildebrand and G. Tenenbaum,*On integers free of large prime factors*, Trans. AMS**296**(1986), no. 1, 265-290. MR**87f:11066****6.**-,*Integers without large prime factors*, Journal de Théorie des Nombres de Bordeaux**5**(1993), 411-484. MR**95d:11116****7.**N. A. Hmyrova,*On polynomials with small prime divisors*, Doklady Akad. Nauk SSSR**155**(1964), 1268-1271, Translation in*Soviet Mathematics*, AMS. MR**28:3975****8.**-,*On polynomials with small prime divisors II*, Izv. Akad. Nauk SSSR Ser. Mat.**30**(1966), 1367-1372. MR**34:7475****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 and Heidelberg, Germany, 1993. MR**96m:11116****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, vol. 106, American Mathematical Society, Providence, Rhode Island, 1971. MR**44:3948****12.**C. Pomerance (ed.),*Cryptology and computational number theory*, Proceedings of Symposia in Applied Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, 1990. MR**92e:94023****13.**-,*Factoring*, Cryptology and Computational Number Theory [12], American Mathematical Society, 1990, pp. 27-48. MR**92b:11089****14.**P. Pritchard,*A sublinear additive sieve for finding prime numbers*, Communications of the ACM**24**(1981), no. 1, 18-23,772. MR**82c:10011****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,*On polynomials with small prime divisors*, Ta[??]skent. Gos. Univ. Nau[??]cn. Trudy; Voprosy Mat.**548**(1977), 87-91,145. MR**58:27845****17.**J. van de Lune and E. Wattel,*On the numerical solution of a differential-difference equation arising in analytic number theory*, Mathematics of Computation**23**(1969), 417-421. MR**40:1050**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
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