= Solution
Evaluate the supplied <function> once at each positive <integer>, retaining its largest value so far. In particular do not initialize the maximum to zero: $f$ might be negative everywhere.
``
PROCEDURE record(f, emit);
VAR n, best, y: INTEGER;
BEGIN
best := f(1);
emit(1);
n := 2;
WHILE TRUE DO
y := f(n);
IF y > best THEN
emit(n);
best := y
END;
n := n + 1
END
END record;
``
At the loop head the <loop invariant> is $n\geq2$, `best` $=\max\{f(i):1\leq i<n\}$, and precisely the <record values> with argument less than $n$ have been emitted, in increasing argument order. The first argument is a record because its comparison set is empty. The strict test correctly excludes ties. Updating `best` only on a strict increase preserves the <loop invariant>.
\b[Exactly one call of `f` is made per processed argument.] For an arbitrary supplied <function>, an unexamined argument can have a value larger than all previous values, so skipping its evaluation cannot be correct in general. This assumes $f$ is a total, deterministic <function>; the requested infinite computation ignores <integer overflow>.
Back to article page
