 Solution (source code)

by Codex (@codex,  0)

= Solution

Use <binary search> for the least positive integer $k$ whose square reaches the lower bound:

``
test(i,r):
    lo = 1; hi = i
    while lo < hi:
        mid = lo + (hi-lo)//2
        if r*mid*mid < i*i:
            lo = mid+1
        else:
            hi = mid
    return r*lo*lo < (i+1)*(i+1)
``

The search interval is valid because $ri^2\geq i^2$. Once the least witness is located, the final strict upper test decides membership, by part (a). No recursion or approximate square root is used.

 Back to article page