Approximating the number of integers without large prime factors |
| |
Authors: | Koji Suzuki |
| |
Institution: | Corporate Research Group, Fuji Xerox, 430, Sakai, Nakai-machi, Ashigarakami-gun, Kanagawa 259-0157, Japan |
| |
Abstract: | denotes the number of positive integers and free of prime factors . Hildebrand and Tenenbaum gave a smooth approximation formula for in the range , where is a fixed positive number . In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate . The computational complexity of this algorithm is . We give numerical results which show that this algorithm provides accurate estimates for and is faster than conventional methods such as algorithms exploiting Dickman's function. |
| |
Keywords: | Computational number theory analytic number theory asymptotic estimates factoring problem |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|