Approximating the number of integers free of large prime factors
Authors:
Simon Hunter and Jonathan Sorenson
Journal:
Math. Comp. 66 (1997), 17291741
MSC (1991):
Primary 11N25, 11Y05; Secondary 11Y16
MathSciNet review:
1423076
Fulltext 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 wellknown 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
(85j:11012), http://dx.doi.org/10.1016/0022314X(83)900021
 3.
N.
G. de Bruijn, The asymptotic behaviour of a function occurring in
the theory of primes, J. Indian Math. Soc. (N.S.) 15
(1951), 25–32. MR 0043838
(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
(87d:11066), http://dx.doi.org/10.1016/0022314X(86)900132
 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 (87f:11066), http://dx.doi.org/10.1090/S00029947198608378111
 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
(95d:11116)
 7.
N.
A. Hmyrova, On polynomials with small prime divisors, Dokl.
Akad. Nauk SSSR 155 (1964), 1268–1271 (Russian). MR 0160764
(28 #3975)
 8.
N.
A. Hmyrova, On polynomials with small prime divisors. II, Izv.
Akad. Nauk SSSR Ser. Mat. 30 (1966), 1367–1372
(Russian). MR
0207660 (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, SpringerVerlag,
Berlin, 1993. MR
1321216 (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 nonresidue, Memoirs of the American Mathematical
Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
(44 #3948)
 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
(92e:94023), http://dx.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
(92b:11089), http://dx.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 (82c:10011), http://dx.doi.org/10.1145/358527.358540
 15.
J. Sorenson, An introduction to prime number sieves, Tech. Report #909, Computer Sciences Department, University of WisconsinMadison, 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
(58 #27845)
 17.
J.
van de Lune and E.
Wattel, On the numerical solution of a
differentialdifference equation arising in analytic number
theory, Math. Comp. 23 (1969), 417–421. MR 0247789
(40 #1050), http://dx.doi.org/10.1090/S00255718196902477893
 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), 128. 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), 2532. MR 13:326f
 4.
 A. Hildebrand, On the number of positive integers and free of prime factors , Journal of Number Theory 22 (1986), 289307. MR 87d:11066
 5.
 A. Hildebrand and G. Tenenbaum, On integers free of large prime factors, Trans. AMS 296 (1986), no. 1, 265290. MR 87f:11066
 6.
 , Integers without large prime factors, Journal de Théorie des Nombres de Bordeaux 5 (1993), 411484. MR 95d:11116
 7.
 N. A. Hmyrova, On polynomials with small prime divisors, Doklady Akad. Nauk SSSR 155 (1964), 12681271, Translation in Soviet Mathematics, AMS. MR 28:3975
 8.
 , On polynomials with small prime divisors II, Izv. Akad. Nauk SSSR Ser. Mat. 30 (1966), 13671372. 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, SpringerVerlag, 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 nonresidue, 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. 2748. MR 92b:11089
 14.
 P. Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), no. 1, 1823,772. MR 82c:10011
 15.
 J. Sorenson, An introduction to prime number sieves, Tech. Report #909, Computer Sciences Department, University of WisconsinMadison, January 1990.
 16.
 N. M. Timofeev, On polynomials with small prime divisors, Ta[??]skent. Gos. Univ. Nau[??]cn. Trudy; Voprosy Mat. 548 (1977), 8791,145. MR 58:27845
 17.
 J. van de Lune and E. Wattel, On the numerical solution of a differentialdifference equation arising in analytic number theory, Mathematics of Computation 23 (1969), 417421. 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:
http://dx.doi.org/10.1090/S0025571897008740
PII:
S 00255718(97)008740
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 CCR9204414.
Computing equipment was provided through a grant from the Holcomb Research Institute.
Article copyright:
© Copyright 1997
American Mathematical Society
