= Integer-square membership in a square-root Beatty sequence
{title2=$i^2\leq rk^2<(i+1)^2$}
For positive integers $i,k,r$, the <floor function> condition $i=\lfloor k\sqrt r\rfloor$ is equivalent to the displayed integer inequalities. Since $r\geq1$, a witness satisfies $k\leq i$. Finding the least $k\geq1$ with $rk^2\geq i^2$ and checking the strict upper bound therefore decides membership by <binary search>. Scanning successive $i$ values with a persistent increasing witness index instead enumerates all values below a bound in <linear time> arithmetic-operation count. Exact integer comparison avoids floating-point errors near an integer boundary.
Back to article page
