Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming (resit) / 2

For $i\ge 1$, $k\ge 1$, and integer $r\ge 1$, all terms are nonnegative, so squaring preserves the inequalities:This gives integer-square membership in a square-root Beatty sequence without evaluating a floating-point square root. Since $\sqrt{r}\ge 1$, any witnessing $k$ satisfies $k\le i$.

Scan candidate output integers in increasing order while maintaining the smallest possible witness:

spectrum(r,n):
    k = 1
    for i = 1,...,n-1:
        while r*k*k < i*i:
            k = k+1
        if r*k*k < (i+1)*(i+1):
            Out.Int(i)

The inner loop supplies the left inequality from part (a), and the final test checks the strict right inequality. This prints each qualifying integer once. The witness index never decreases and is at most $i$ after the inner loop, so its total number of increments is at most $n-1$. Consequently the whole nonrecursive program uses $O(n)$ integer arithmetic operations, not $O(n)$ iterations of a fresh search. Exact products or overflow-safe comparisons are required; arbitrary-precision bit costs depend on operand sizes.

Before testing candidate $i$, every earlier integer has been printed exactly when it belongs to the spectrum, and every positive $h<k$ satisfies $r{h}^2<i^2$. During the inner loop that exclusion remains true: an excluded candidate is passed over only after checking its square.

At termination of the inner loop, $r{k}^2\ge i^2$, so $k$ is the least positive possible witness. If its square is already at least $(i+1{)}^2$, every larger witness is too large as well; otherwise it satisfies both required inequalities and $i$ is printed. Advancing $i$ preserves the earlier-witness exclusion because the new lower bound only increases. These loop invariants establish both completeness and absence of extra outputs.

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 $r{i}^2\ge 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.

Maintain that all positive $h<\mathrm{lo}$ fail $r{h}^2\ge i^2$, while hi satisfies that inequality; its least satisfying integer lies in $[\mathrm{lo},\mathrm{hi}]$. Monotonicity of $r{k}^2$ in positive $k$ validates both updates. At exit the endpoints agree and identify exactly that least integer.

The loop variant hi-lo decreases on every iteration and is at least halved up to rounding. Starting with at most $i$ candidates therefore needs $O(\log (i+1))$ arithmetic operations, conventionally $O(\log i)$ for $i\ge 2$. For $i=1$ the loop is empty. The final upper-bound check proves the returned Boolean is the required membership answer.