Memoisation over floor-division blocks

Some sums run over every integer from 1 to n, applying floor(n / d) at each step. Computed one term at a time, that is an $O(n)$ loop. But floor(n / d) does not actually take n distinct values as d ranges from 1 to n; it takes only $O(\sqrt{n})$ of them, and every d that shares a quotient can be handled together in one step.

Why only O(sqrt(n)) quotients exist

Split the range of d at $\sqrt{n}$. For d from 1 to $\sqrt{n}$, there are only $\sqrt{n}$ possible values of d itself, so there are at most $\sqrt{n}$ distinct quotients among them, regardless of what those quotients equal. For d greater than $\sqrt{n}$, the quotient floor(n / d) is itself smaller than $\sqrt{n}$, since d * floor(n/d) <= n forces floor(n/d) <= n / d < sqrt(n). That leaves at most $\sqrt{n}$ possible quotient values on this side too. Together, the two halves bound the total number of distinct quotients by roughly $2\sqrt{n}$, which is $O(\sqrt{n})$.

Finding one block's boundary

Start at d = 1 and compute q = n // d. Every later d' with n // d' == q forms one block, and the largest such d' is n // q (as long as q is not zero; once q is zero, every remaining d up to n shares that same zero quotient). Once you know the block's last d, jump straight there and start the next block one past it.

Take n = 10. At d = 1, q = 10, and the block's last d is 10 // 10 = 1, so this block is just {1}. At d = 2, q = 5, and the block's last d is 10 // 5 = 2, so this block is {2}. At d = 3, q = 3, and the last d is 10 // 3 = 3, so this block is {3}. At d = 4, q = 2, and the last d is 10 // 2 = 5, so this block is {4, 5}, both sharing quotient 2. At d = 6, q = 1, and the last d is 10 // 1 = 10, so the final block is {6, 7, 8, 9, 10}, all sharing quotient 1. Five blocks cover all ten values of d, not because ten happens to be small, but because that is the actual number of distinct quotients here.

Summing a block's contribution

Inside one block, every d contributes the same quotient q, so the block's total is q times the number of d values in it, not the sum of q computed separately for each one.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    if not data:7        return8
9    n = int(data[0])10
11    # Compute sum of floor(n / d) for d = 1 to n, using O(sqrt(n)) blocks12    # instead of an O(n) loop over every divisor d.13    total = 014    d = 115
16    while d <= n:17        q = n // d  # the quotient shared by this whole block of divisors18
19        # Every d' in this block satisfies n // d' == q. The largest such d'20        # is n // q (when q > 0); beyond it the quotient drops below q.21        next_d = n // q if q > 0 else n22
23        count = next_d - d + 124        total += q * count25
26        d = next_d + 127
28    print(f"Sum of floor({n}/d) for d=1 to {n}: {total}")29
30
31if __name__ == "__main__":32    main()

100

Sum of floor(100/d) for d=1 to 100: 482

Following the same five blocks by hand for n = 10: block {1} contributes 10 * 1 = 10, block {2} contributes 5 * 1 = 5, block {3} contributes 3 * 1 = 3, block {4, 5} contributes 2 * 2 = 4, and block {6, 7, 8, 9, 10} contributes 1 * 5 = 5. The total is 10 + 5 + 3 + 4 + 5 = 27, matching a direct sum of floor(10 / d) over every d from 1 to 10. The program computes the same sum for n = 100, jumping between roughly $2\sqrt{100} = 20$ blocks instead of summing 100 individual terms.

Memoisation over blocks

When a computation depends on d only through its quotient floor(n / d), you never need to repeat that computation for every d inside a block. Compute it once per distinct quotient value, then multiply or combine it across the whole block. If a block covers 40 values of d that all produce the same quotient, one computation covers all 40, instead of 40 separate ones.

This is exactly how the divisor-summatory function is computed efficiently. The sum of tau(i), the number of divisors of i, for i from 1 to n, equals the sum of floor(n / d) for d from 1 to n: each divisor d of some i <= n is counted once for every multiple of d up to n, and there are exactly floor(n / d) such multiples. Grouping that sum into $O(\sqrt{n})$ blocks, instead of counting multiples one divisor at a time, turns an $O(n)$ computation into $O(\sqrt{n})$.

Common mistakes

The most common mistake is getting the block boundary formula wrong. The largest d sharing quotient q = n // d is n // q, but only while q is positive; if q is zero, the entire remaining range from the current d up to n shares that zero quotient, and the formula n // q cannot be used directly, since it would divide by zero.

Another mistake is applying this technique to floor(i / d) for a single fixed d as i ranges from 1 to n. That sum has roughly n / d distinct quotients, not $O(\sqrt{n})$: the block-counting argument in this lesson relies on d itself being the value that varies from 1 to n, with n held fixed. Confusing which quantity is fixed and which one varies leads to a technique that runs correctly but does not actually save any time.

A third mistake is integer overflow when multiplying a quotient by a large block size. In Python this never causes wraparound, since integers grow as needed, but in other languages the product needs a wide enough integer type.

Where this shows up

This block-jumping trick sometimes goes by the name "the harmonic lemma," since summing floor(n / d) over every d from 1 to n is closely related to the harmonic series: each term is roughly n / d, and the whole sum is close to n * ln(n). What the blocks buy you is not a smaller sum, but a smaller number of additions needed to compute it exactly.

It also generalizes past a single variable. A problem that needs floor(n / d) for many different values of n, or a two-dimensional sum involving floor(n / i) and floor(m / i) together, can walk both quantities' blocks at once, stopping at whichever boundary comes first. That keeps the total number of steps at $O(\sqrt{n} + \sqrt{m})$ instead of $O(\sqrt{n} \cdot \sqrt{m})$.

Recap

floor(n / d) takes only $O(\sqrt{n})$ distinct values as d ranges from 1 to n, because small values of d are few in number and large values of d force a small quotient. Finding each block's boundary with n // q and multiplying the shared quotient by the block's size computes a sum over all of d in $O(\sqrt{n})$ time. The same grouping is what makes the divisor-summatory function computable without counting multiples one divisor at a time.