Test each positive candidate divisor and count the successful remainder tests:The loop invariant is and , where denotes
def divisors(n: Int): Int = {
require(n >= 1)
var candidate = 1L
var count = 0
while (candidate <= n.toLong) {
if (n.toLong % candidate == 0L) count += 1
candidate += 1L
}
count
}candidate. A successful test adds exactly the new divisor; an unsuccessful test leaves the count unchanged. The loop variant is , which decreases by one. At termination , so the returned value is . A Long loop counter prevents the increment after the last positive Int candidate from wrapping around.Use a strict record test; tying the previous record is not enough:At the start of an iteration,
def emitHighlyComposite(): Unit = {
var candidate = 1
var best = 0
while (true) {
val count = divisors(candidate)
if (count > best) {
emit(candidate)
best = count
}
candidate += 1
}
}best is the maximum divisor count among the positive integers below candidate, taking the maximum of the empty family as zero. The already emitted values are exactly the highly composite numbers in that range, in increasing order. The next count exceeds best precisely when this candidate is a new strict record. Updating the record and advancing the candidate preserves both assertions. The program deliberately has no termination requirement; integer overflow in this unbounded enumeration is ignored as directed by the source.By the time the candidate is emitted, every positive integer has been examined. The straightforward divisor routine makes exactly remainder tests on . Consequently the total number isand the time is when remainder tests and the other fixed-width operations have constant cost and printing is cheap. Emitting only record candidates does not avoid computing the divisor count of the intervening candidates.
Every positive divisor has a unique prime factorization with . Conversely every such exponent choice gives a divisor. The exponent choices are independent, so the product rule givesFor the factorization is empty, and the empty product is one, corresponding to the divisor one.
Remove each prime power as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:At an outer-loop boundary, write , where is the product of the prime powers already removed. The invariant states that
def divisors(n: Int): Int = {
require(n >= 1)
var remaining = n
var factor = 2
var result = 1
while (factor.toLong * factor.toLong <= remaining.toLong) {
var exponent = 0
while (remaining % factor == 0) {
remaining /= factor
exponent += 1
}
result *= exponent + 1
factor += 1
}
if (remaining > 1) result *= 2
result
}result is , every prime divisor of is smaller than factor, and remaining has no prime divisor smaller than factor. Thus if factor divides remaining, it is prime; a composite factor would have a smaller prime divisor, contrary to the invariant.During the inner loop, with fixed, . Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-loop variant. On leaving the inner loop the complete power has been removed; multiplying the result by
exponent + 1 uses part (d) and reestablishes the outer invariant after advancing factor. The outer factor increases and can never exceed the original while its guard holds, proving termination.At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than
factor. It therefore contributes one final factor of two. A remainder of one contributes nothing. The algorithm returns using constant auxiliary space and no array. The widened multiplication in the loop guard prevents an Int overflow in the square test.The factorization-based version should produce the later outputs faster in this cost model. For an input , it performs at most trial-factor tests and successful divisions, because each successful division removes a factor at least two. The square test uses multiplication, so it does not introduce an extra division on every loop test.
Across all candidates through , the number of costly division or remainder operations is therefore at mostcompared with remainder operations for the straightforward routine. Small cases can still be affected by constant overhead; the conclusion concerns the growing enumeration workload, not a promise that every single call is faster.
Articles by others on the same topic
There are currently no matching articles.