Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $\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 [Enhancements On Off] (What's this?)

  • 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 $\le x$ and free of prime factors $> y$, 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 $k$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

Similar Articles

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

American Mathematical Society