An Algorithm for Ennola's Second Theorem and Counting Smooth Numbers in Practice

arXiv2208.01725MaRDI QIDQ6406800FDOQ6406800

Authors: Chloe Makdad, Jonathan P. Sorenson 

Publication date: 2 August 2022

Abstract: Let $Psi(x,y)$ count the number of positive integers $nlex$ such that every prime divisor of $n$ is at most $y$. Given inputs $x$ and $y$, what is the best way to estimate $Psi(x,y)$? We address this problem in three ways: with a new algorithm to estimate $Psi(x,y)$, with a performance improvement to an established algorithm, and with empirically based advice on how to choose an algorithm to estimate $Psi$ for the given inputs. Our new algorithm to estimate $Psi(x,y)$ is based on Ennola's second theorem [Ennola69], which applies when $y<(logx{)}^{3/4-epsilon}$ for $epsilon>0$. It takes $O(y^2/logy)$ arithmetic operations of precomputation and $O(ylogy)$ operations per evaluation of $Psi$. 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 $loglogx$, by applying Newton's method in a new way. And finally we give our empirical advice based on five algorithms to compute estimates for $Psi(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 $epsilon>0$, for example, that cannot be programmed directly.

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

This page was built for publication: An Algorithm for Ennola's Second Theorem and Counting Smooth Numbers in Practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406800)