Harmonic Lemma

Imagine looping i = 1..n and reading the integer part of n divided by i, i.e., floor(n/i). At first glance, this seems to need O(n) steps. The Harmonic Lemma reveals a hidden structure: floor(n/i) does not change at every i; it stays constant over long stretches (blocks) and only changes about 2√n times. This lets us jump over entire blocks at once. The consequence is powerful: many sums involving floor(n/i) can be evaluated in O(√n) instead of O(n). Hook: Instead of reading every page of a 1000-page book, suppose you could read only the pages where the topic changes—maybe just 60–70 pages. The Harmonic Lemma is like flipping to those change points for floor divisions. Concept: The key observation is that if floor(n/i) = v, then all i in some contiguous interval $\begin{pmatrix} l \\ r \end{pmatrix}$ share the same value v. With simple algebra, we can compute r from l (or l from v) in O(1). That means a for loop can jump directly from one block to the next, processing each block in constant time. Example: To compute S = ∑_{i=1}^{n} floor(n/i), we iterate over blocks $\begin{pmatrix} l \\ r \end{pmatrix}$ where floor(n/i) is constant v. We add $v·(r$−l+1) to S and jump l to r+1. This yields an O(√n) algorithm with tiny memory.

Think of pouring candies (n candies) into bags of sizes i = 1, 2, 3, …; the number of full bags you can fill is floor(n/i). For small i, the bag is small, so you fill many bags (large value). For large i, the bag is large, so you fill few bags (small value). As i increases, floor(n/i) decreases, but not one-by-one every step. It often stays the same across several consecutive i’s—those are blocks. For example, with n = 100, floor(100/1)=100, floor(100/2)=50, floor(100/3)=33, …; near i = 50..100, many consecutive i give 1 or 2. If you only care about how many full bags you get (the value), you can jump to the next i where that number changes, skipping everything in between. A useful mental picture: Write all divisors of numbers up to n as grid points (i, j) with $i·j$ ≤ n. Counting by rows (fix i) is like summing floor(n/i); counting by columns (fix floor(n/i)) groups many points together. The border $i·j$ = n is a hyperbola, which is why this trick is sometimes called the hyperbola method. Below the hyperbola, points cluster heavily near the axes, meaning many i share the same floor value—perfect for block jumps. In daily life, if bus arrivals are grouped in time windows, you don’t check every minute; you check when the schedule changes. Likewise, we step through i only where floor(n/i) changes, which happens about 2√n times.

Use this technique when your summation or DP transitions repeatedly use terms of the form \lfloor n/i \rfloor or n/i as an index/value. Common cases:

• Summatory divisor problems: Compute \su$m_{i=1}^{n}$ d(i) using the identity \su$m_{i=1}^{n}$ d(i) = \su$m_{k=1}^{n}$ \lfloor n/k \rfloor.
• Hyperbola-method rearrangements: Split lattice point counts under $i·j$ ≤ n into two short sums around $\sqrt{n}$.
• Weighted sums: Evaluate \su$m_{i=1}^{n}$ a(i),\lfloor n/i \rfloor using block decomposition plus a prefix sum of a(i).
• DP with floor transitions: If transitions depend only on v = \lfloor n/i \rfloor, you can process ranges with the same v together.
• Sieve-like computations: In multiplicative-function summatory problems that involve \lfloor n/i \rfloor (e.g., using Möbius or Euler’s totient in convolution identities), block iteration reduces runtime from O(n) to O($\sqrt{n}$) when combined with precomputed prefix sums or small sieves. Aim for this method when constraints make O(n) too slow (n up to 1e12 in math-y problems, or n up to 1e7–1e8 with tight time limits) and the structure involves integer division by i.