论文标题
Ennola第二个定理的算法，实际上计数平滑数字
An Algorithm for Ennola's Second Theorem and Counting Smooth Numbers in Practice
论文作者
论文摘要
令$ψ（x，y）$计数正整数$ n \ le x $的数量，以使$ n $的每个主要除数最多都是$ y $。给定输入$ x $和$ y $，估计$ψ（x，y）$的最佳方法是什么？我们以三种方式解决了这个问题：使用新的算法来估计$ψ（x，y）$，对已建立的算法进行性能提高，并基于基于经验的建议，如何选择算法以估算给定输入的算法$ψ$。 我们的新算法估计$ψ（x，y）$基于Ennola的第二个定理[ENNOLA69]，该定理适用于$ y <（\ log x）^{3/4-ε} $ for $ε> 0 $。每次评估$ o（y^2/\ log y）$算术的算术操作和$ o（y \ log y）$ $（y \ log y）$每评估$ψ$。 我们通过以新的方式应用了与$ \ log \ log x $成比例的因素来展示基于Hildebrand and Tenenbaum [1986]的鞍点方法加快算法HT的速度。 最后，我们根据五种算法给出了经验建议，以计算$ψ（x，y）$的估计值。这里的挑战是，适用性范围（如定理中给出的范围），通常包括未知常数或$ε> 0 $的小值，例如，无法直接编程。
Let $Ψ(x,y)$ count the number of positive integers $n\le x$ such that every prime divisor of $n$ is at most $y$. Given inputs $x$ and $y$, what is the best way to estimate $Ψ(x,y)$? We address this problem in three ways: with a new algorithm to estimate $Ψ(x,y)$, with a performance improvement to an established algorithm, and with empirically based advice on how to choose an algorithm to estimate $Ψ$ for the given inputs. Our new algorithm to estimate $Ψ(x,y)$ is based on Ennola's second theorem [Ennola69], which applies when $y< (\log x)^{3/4-ε}$ for $ε>0$. It takes $O(y^2/\log y)$ arithmetic operations of precomputation and $O(y\log y)$ operations per evaluation of $Ψ$. We show how to speed up Algorithm HT, which is based on the saddle-point method of Hildebrand and Tenenbaum [1986], by a factor proportional to $\log\log x$, by applying Newton's method in a new way. And finally we give our empirical advice based on five algorithms to compute estimates for $Ψ(x,y)$.The challenge here is that the boundaries of the ranges of applicability, as given in theorems, often include unknown constants or small values of $ε>0$, for example, that cannot be programmed directly.
