An Algorithm and Estimates for the Erd\H{o}s-Selfridge Function (work in progress)

Let $p(n)$ denote the smallest prime divisor of the integer $n$. Define the function $g(k)$ to be the smallest integer $>k+1$ such that $p(\left(\genfrac{}{}{0px}{}{g(k)}{k}\right))>k$. So we have $g(2)=6$ and $g(3)=g(4)=7$. In this paper we present the following new results on the Erd\H{o}s-Selfridge function $g(k)$: We present a new algorithm to compute the value of $g(k)$, and use it to both verify previous work and compute new values of $g(k)$, with our current limit being $$g(323)=1698297710446041211456325122499.$$ We define a new function $\widehat{g}(k)$, and under the assumption of our Uniform Distribution Heuristic we show that $$\log g(k)=\log \widehat{g}(k)+O(\log k)$$ with high “probability”. We also provide computational evidence to support our claim that $\widehat{g}(k)$ estimates $g(k)$ reasonably well in practice. There are several open conjectures on the behavior of $g(k)$ which we are able to prove for $\widehat{g}(k)$, namely that $$0.525\dots +o(1)\le \frac{\log \widehat{g}(k)}{k\mathrm{/}\log k}\le 1+o(1),$$ and that $$\underset{k\to \mathrm{\infty }}{\mathrm{lim\hspace{0.17em}sup}}\frac{\widehat{g}(k+1)}{\widehat{g}(k)}=\mathrm{\infty }\mathrm{.}$$ Let $G(x,k)$ count the number of integers $n\le x$ such that $p(\left(\genfrac{}{}{0px}{}{n}{k}\right))>k$. Unconditionally, we prove that for large $x$, $G(x,k)$ is asymptotic to $x\mathrm{/}\widehat{g}(k)$. And finally, we show that the running time of our new algorithm is at most $g(k)\exp [-c(k\log \log k)\mathrm{/}(\log k{)}^2(1+o(1))]$ for a constant $c>0$.