Evaluate the supplied function once at each positive integer, retaining its largest value so far. In particular do not initialize the maximum to zero: might be negative everywhere.At the loop head the loop invariant is ,
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;best , and precisely the record values with argument less than 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.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 is a total, deterministic function; the requested infinite computation ignores integer overflow.Test each possible positive divisor directly:For , the loop invariant is and
PROCEDURE divisors(n: INTEGER): INTEGER;
VAR i, count: INTEGER;
BEGIN
i := 1; count := 0;
WHILE i <= n DO
IF n MOD i = 0 THEN count := count + 1 END;
i := i + 1
END;
RETURN count
END divisors;count . Testing adds exactly the next possible divisor. The loop variant decreases, and the divisor in MOD is always positive. At exit the interval contains every positive divisor. This computes the divisor function using remainder operations, time, and auxiliary space.By the time
print(n) is called, record has evaluated divisors(i) once for every . In the unit-cost model, the total number of remainder tests isThe record values comparisons add only work, and output is cheap by assumption. The elapsed time is . This measures time to reach a given highly composite number, rather than time as a function of the number of printed records.By unique prime factorization, a positive divisor has precisely the formThere are independent choices for each prime exponent; different choices give different divisors, and every divisor occurs. The multiplication principle therefore gives . For , the empty product is , giving its one positive divisor.
Use trial division on a shrinking residual. Once the trial divisor exceeds its square root, any residual larger than one is itself prime.For the outer loop invariant, let be the set of primes below
PROCEDURE divisors(n: INTEGER): INTEGER;
VAR residual, trial, exponent, answer: INTEGER;
BEGIN
residual := n; trial := 2; answer := 1;
WHILE trial * trial <= residual DO
exponent := 0;
WHILE residual MOD trial = 0 DO
residual := residual DIV trial;
exponent := exponent + 1
END;
answer := answer * (exponent + 1);
trial := trial + 1
END;
IF residual > 1 THEN answer := 2 * answer END;
RETURN answer
END divisors;trial and their exponents in the original . Thenand residual has no prime factor below trial. If trial divides the residual it must therefore be prime: a composite trial value would have a smaller prime factor, contradicting this clause. If it does not divide, the zero exponent contributes the factor .For the inner loop invariant, let be the residual on entry. Then . Each exact division reduces the positive residual by at least a factor of two, so this loop terminates. At exit the exponent is the full multiplicity of
trial; multiplying by exponent+1 preserves the outer loop invariant. The outer loop terminates because trial increases and residual never increases. When it exits, a composite residual would have a prime factor at most its square root, yet every smaller trial factor has already been excluded. Hence the residual is or a single remaining prime of exponent .The procedure computes in unit-cost time and auxiliary space, with the separate successful divisions bounded by . No array or table of primes is needed, and correctly returns .
The second procedure should reach large outputs faster, because the first makes exactly expensive
MOD operations when processing argument , whereas the second tries only up to the square root of a shrinking residual, with at most successful DIV operations. Each successful division also requires a successful MOD test; each outer iteration adds one final unsuccessful MOD test. Thus its expensive-operation count is per argument, and at most cumulatively through argument , compared with for direct counting.The speedup is not an assertion that every single call uses fewer divisions: for , the second code makes three
MOD tests and two DIV operations, while the first makes four MOD tests. Small constant costs can go either way. The many small prime factors in highly composite numbers also shrink the residual early, which often helps further; the cumulative comparison includes every preceding argument, not only the printed records. Articles by others on the same topic
There are currently no matching articles.