Retsy Boss VIII's Star Fitting Homage

After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current $58$ states. As an homage to the original flag design, Retsy wants to select $58$ stars from the square grid that are all at most some distance $R$ from a point on the plane. What is the minimum distance $R$ that Retsy can use?

Thankfully for Retsy Boss VIII, her namesake left her the Python code to run the optimization to find the number of stars given $h,$ $k$ and $R.$ Also, fortunately for Retsy Boss VIII she knew to look at OEIS to look up the integer sequence A000328, which captures the case of $h=k=0$ and $R \in \mathbb{N},$ to give her a decent idea of where to start. In particular, we see that $N(0,0,4) = 49$ and $N(0,0,5)=81,$ so let's start looking for $R \in [4,5].$ In particular, she wants to find $$R^* = \inf \left\{ R \in [4,5] \mid N^*(R) = \sup_{(h,k) \in [0,1]^2} N(h,k,R) \geq 58 \right\}.$$

Retsy didn't want to exhaustively search the entire phase space, so first she went about implementing a secant method update to arrive at some point $R$ for which $N^*(R) = 58.$ In particular, let's let $R_0 = 4,$ $R_1 = 5$ and $$R_{n+1} = \frac{R_{n-1} N^*(R_n) - R_n N^*(R_{n-1}) + 58 (R_n - R_{n-1})}{N^*(R_n) - N^*(R_{n-1})}.$$ Note that relatively quickly we arrive at some value with $N^*(R) = 58,$ that is,

$n$	$R_n$	$N^*(R_n)$
$0$	$4$	$49$
$1$	$5$	$81$
$2$	$4.20689655\dots$	$59$
$3$	$4.17084639\dots$	$58$

That is all well and good, but Retsy VIII wants the minimal such value of $R$ such that $N^*(R) = 58.$ Now she turns to a binary search of the interval $[a_0,b_0] = [4, 4.17084639],$ to within a tolerance of $\varepsilon = 10^{-6}.$ For each $n,$ she defines $c_n = \frac{a_n+b_n}{2}.$ If $N^*(c_n) \lt 58,$ then she defines $a_{n+1} = c_n$ and $b_{n+1} = b_n;$ however if $N^*(c_n) = 58,$ then she defines $a_{n+1} = a_n$ and $b_{n+1} = c_n.$ We can stop as soon as

$n$	$a_n$	$b_n$	$c_n$	$N^*(c_n)$
$0$	$4$	$4.17084639$	$4.08542320$	$56$
$1$	$4.08542320$	$4.17084639$	$4.12813480$	$57$
$2$	$4.12813480$	$4.17084639$	$4.14949060$	$57$
$3$	$4.14949060$	$4.17084639$	$4.16016850$	$58$
$4$	$4.14949060$	$4.16016850$	$4.15482955$	$57$
$5$	$4.15482955$	$4.16016850$	$4.15749902$	$58$
$6$	$4.15482955$	$4.15749902$	$4.15616428$	$58$
$7$	$4.15482955$	$4.15616428$	$4.15549691$	$58$
$8$	$4.15482955$	$4.15549691$	$4.15516323$	$57$
$9$	$4.15516323$	$4.15549691$	$4.15533007$	$58$
$10$	$4.15516323$	$4.15533007$	$4.15524665$	$58$
$11$	$4.15516323$	$4.15524665$	$4.15520494$	$58$
$12$	$4.15516323$	$4.15520494$	$4.15518409$	$57$
$13$	$4.15518409$	$4.15520494$	$4.15519451$	$58$
$14$	$4.15518409$	$4.15519451$	$4.15518930$	$57$
$15$	$4.15518930$	$4.15519451$	$4.15519191$	$57$
$16$	$4.15519191$	$4.15519451$	$4.15519321$	$58$
$17$	$4.15519191$	$4.15519321$	$4.15519256$	$58$

So we see that the optimal value of $R^*$ is about $4.15519256$ to within a tolerance of $\varepsilon = 10^{-6}.$ At this point, we can use map a contour plot, shown below, similar to what we did for the Classic problem. It is hard to discern, but the only place that the maximum is attained (up to the various symmetries of the $N$ function) when $R = 4.15519256$ is in a small neighborhood of the point $(h,k) = (1/2, 1/8)$ (seem familiar ... wink, wink?). If we were to graph the circle of radius $R = 4.15519256$ centered at $(1/2, 1/8),$ we see that it ever so slightly includes the lattice points $(-1,4),$ $(2,4),$ $(0,-4)$ and $(1,-4).$ In particular, since we see that the distance from $(1/2, 1/8)$ to any of these four lattices points is exactly the same, we can reduce the value of $R$ to precise that distance and maintain a value of $N^*(R) = 58,$ and hence the minimum distance that Retsy Boss VIII can use to honor her forebear's design is exactly $$R^* = \sqrt{0.5^2 + 4.125^2} = \sqrt{1.5^2 + 3.875^2} = \frac{\sqrt{1105}}{8} \approx 4.155192534648665\dots.$$