Approximating the number of integers free of large prime factors期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Approximating the number of integers free of large prime factors

Authors:	Simon Hunter Jonathan Sorenson

Institution:	Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208 Jonathan Sorenson ; Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana 46208

Abstract:	Define $\Psi (x,y)$ to be the number of positive integers $n\le x$ such that has no prime divisor larger than . 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.

Keywords:	Psixyology integer factoring analytic number theory algorithmic number theory computational number theory

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文