Let
$p\left(n\right)$
denote the smallest prime divisor of the integer
$n$. Define the
function
$g\left(k\right)$ to be the
smallest integer
$>k+1$
such that
$p\left(\left(\genfrac{}{}{0.0pt}{}{g\left(k\right)}{k}\right)\right)>k$.
We present a new algorithm to compute the value of
$g\left(k\right)$,
and use it to both verify previous work and compute new values of
$g\left(k\right)$, with
our current limit being
$$g\left(375\right)=12863999653788432184381680413559.$$
We prove that our algorithm runs in time sublinear in
$g\left(k\right)$, and
under the assumption of a reasonable heuristic, its running time is
$$g\left(k\right)exp\left[c\left(kloglogk\right)\u2215{\left(logk\right)}^{2}\left(1+o\left(1\right)\right)\right]\phantom{\rule{1em}{0ex}}\text{for}c0.$$
