{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:36:10Z","timestamp":1776785770890,"version":"3.51.2"},"reference-count":18,"publisher":"American Mathematical Society (AMS)","issue":"254","license":[{"start":{"date-parts":[[2006,12,2]],"date-time":"2006-12-02T00:00:00Z","timestamp":1165017600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n \n \n \n \n \n \u03a8\n \n <\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Psi (x,y)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n denotes the number of positive integers\n \n \n \n \n \n \u2264\n \n <\/mml:mo>\n x<\/mml:mi>\n <\/mml:mrow>\n \\leq x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and free of prime factors\n \n \n \n \n ><\/mml:mo>\n y<\/mml:mi>\n <\/mml:mrow>\n >y<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Hildebrand and Tenenbaum gave a smooth approximation formula for\n \n \n \n \n \n \u03a8\n \n <\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Psi (x,y)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in the range\n \n \n \n \n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n x<\/mml:mi>\n \n )<\/mml:mo>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \n \u03f5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n ><\/mml:mo>\n y<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n x<\/mml:mi>\n <\/mml:mrow>\n (\\log x)^{1+\\epsilon }> y \\leq x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \u03f5\n \n <\/mml:mi>\n \\epsilon<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a fixed positive number\n \n \n \n \n \n \u2264\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n \\leq 1\/2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate\n \n \n \n \n \n \u03a8\n \n <\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Psi (x,y)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The computational complexity of this algorithm is\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n O(\\sqrt {(\\log x)(\\log y)})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We give numerical results which show that this algorithm provides accurate estimates for\n \n \n \n \n \n \u03a8\n \n <\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n y<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Psi (x,y)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and is faster than conventional methods such as algorithms exploiting Dickman\u2019s function.\n <\/p>","DOI":"10.1090\/s0025-5718-05-01798-9","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T11:05:20Z","timestamp":1140001520000},"page":"1015-1024","source":"Crossref","is-referenced-by-count":4,"title":["Approximating the number of integers without large prime factors"],"prefix":"10.1090","volume":"75","author":[{"given":"Koji","family":"Suzuki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2005,12,2]]},"reference":[{"issue":"246","key":"1","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1090\/S0025-5718-03-01501-1","article-title":"Prime sieves using binary quadratic forms","volume":"73","author":"Atkin, A. O. L.","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"216","key":"2","doi-asserted-by":"publisher","first-page":"1701","DOI":"10.1090\/S0025-5718-96-00775-2","article-title":"Asymptotic semismoothness probabilities","volume":"65","author":"Bach, Eric","year":"1996","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/BFb0054856","article-title":"Bounding smooth integers (extended abstract)","author":"Bernstein, Daniel J.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646574"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","article-title":"On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u201d","volume":"17","author":"Canfield, E. R.","year":"1983","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"191","key":"5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.2307\/2008795","article-title":"A differential delay equation arising from the sieve of Eratosthenes","volume":"55","author":"Cheer, A. Y.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/S1385-7258(51)50008-2","article-title":"On the number of positive integers \u2264\ud835\udc65 and free of prime factors >\ud835\udc66","volume":"54","author":"de Bruijn, N. G.","year":"1951","journal-title":"Nederl. Akad. Wetensch. Proc. Ser. A"},{"key":"7","first-page":"25","article-title":"The asymptotic behaviour of a function occurring in the theory of primes","volume":"15","author":"de Bruijn, N. G.","year":"1951","journal-title":"J. Indian Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0019-5839","issn-type":"print"},{"key":"8","unstructured":"K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv F\u00f6r Matematik, Astromi Fysik. Band 22 A, no. 10, 1-14, 1930."},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0022-314X(86)90013-2","article-title":"On the number of positive integers \u2264\ud835\udc65 and free of prime factors >\ud835\udc66","volume":"22","author":"Hildebrand, Adolf","year":"1986","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"729","DOI":"10.2307\/2000551","article-title":"On the local behavior of \u03a8(\ud835\udc65,\ud835\udc66)","volume":"297","author":"Hildebrand, Adolf","year":"1986","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/2000573","article-title":"On integers free of large prime factors","volume":"296","author":"Hildebrand, Adolf","year":"1986","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.5802\/jtnb.101","article-title":"Integers without large prime factors","volume":"5","author":"Hildebrand, Adolf","year":"1993","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"issue":"220","key":"13","doi-asserted-by":"publisher","first-page":"1729","DOI":"10.1090\/S0025-5718-97-00874-0","article-title":"Approximating the number of integers free of large prime factors","volume":"66","author":"Hunter, Simon","year":"1997","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"187","key":"14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.2307\/2008355","article-title":"Numerical solution of some classical differential-difference equations","volume":"53","author":"Marsaglia, George","year":"1989","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"15","series-title":"Memoirs of the American Mathematical Society, No. 106","volume-title":"Numbers with small prime factors, and the least $k$th power non-residue","author":"Norton, Karl K.","year":"1971"},{"key":"16","doi-asserted-by":"crossref","unstructured":"R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13, 242-247, 1938.","DOI":"10.1112\/jlms\/s1-13.4.242"},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/10722028_36","article-title":"A fast algorithm for approximately counting smooth numbers","author":"Sorenson, Jonathan P.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"issue":"246","key":"18","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1090\/S0025-5718-03-01571-0","article-title":"An estimate for the number of integers without large prime factors","volume":"73","author":"Suzuki, Koji","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01798-9\/S0025-5718-05-01798-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01798-9\/S0025-5718-05-01798-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:36:01Z","timestamp":1776782161000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01798-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,2]]},"references-count":18,"journal-issue":{"issue":"254","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["S0025-5718-05-01798-9"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-05-01798-9","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2005,12,2]]}}}