The Language of Divisors

Pillar: Shape — "A double sum \(\sum_i \sum_{d \mid i} f(d)\) is a 2D grid. Swapping summation order = transposing the matrix = reading the same data in a different SHAPE."

---

Why This Lesson

Every remaining lesson in this chapter — multiplicative functions, Dirichlet convolution, Mobius inversion, the floor staircase — uses the notation \(\sum_{d \mid n} f(d)\) and the technique of swapping summation order in double divisor sums. If you can't read and manipulate these expressions fluently, the rest of Ch9 will feel like fighting the notation instead of learning the ideas.

This lesson has one goal: make you completely comfortable with divisor sums and the summation swap. No new algorithms. No deep theory. Just the notation, the core technique, and enough practice to make it automatic.

---

Divisor Sums: The Notation

The expression \(\sum_{d \mid n} f(d)\) means: "sum \(f(d)\) over every positive divisor \(d\) of \(n\)."

Take \(n = 12\). Its divisors are \(1, 2, 3, 4, 6, 12\). So:

\[\sum_{d \mid 12} f(d) = f(1) + f(2) + f(3) + f(4) + f(6) + f(12)\]

That's it. The vertical bar \(\mid\) means "divides," and you range over all positive integers that divide \(n\).

Two classic choices of \(f\) give two famous functions.

The Divisor Count \(\tau(n)\)

Set \(f(d) = 1\). Then \(\sum_{d \mid n} 1\) just counts how many divisors \(n\) has. This is the divisor counting function \(\tau(n)\) (also written \(d(n)\) or \(\sigma_0(n)\)).

\[\tau(12) = \sum_{d \mid 12} 1 = 6\]

because \(12\) has six divisors: \(1, 2, 3, 4, 6, 12\).

The Divisor Sum \(\sigma(n)\)

Set \(f(d) = d\). Then \(\sum_{d \mid n} d\) adds up all the divisors of \(n\). This is the divisor sum function \(\sigma(n)\) (also written \(\sigma_1(n)\)).

\[\sigma(12) = \sum_{d \mid 12} d = 1 + 2 + 3 + 4 + 6 + 12 = 28\]

These two examples — \(f(d) = 1\) and \(f(d) = d\) — are enough to illustrate everything in this lesson. The technique works for any \(f\).

---

The Double Sum

Now consider a harder question: what is \(\sum_{i=1}^{n} \tau(i)\)? The total number of divisors across all integers from \(1\) to \(n\).

Expand the definition of \(\tau\):

\[\sum_{i=1}^{n} \tau(i) = \sum_{i=1}^{n} \sum_{d \mid i} 1\]

This is a double sum. For each \(i\) from \(1\) to \(n\), you loop over the divisors of \(i\) and add \(1\) for each one. Trace it for \(n = 6\):

\(i\)	Divisors of \(i\)	\(\tau(i)\)
\(1\)	\(1\)	\(1\)
\(2\)	\(1, 2\)	\(2\)
\(3\)	\(1, 3\)	\(2\)
\(4\)	\(1, 2, 4\)	\(3\)
\(5\)	\(1, 5\)	\(2\)
\(6\)	\(1, 2, 3, 6\)	\(4\)

Total: \(1 + 2 + 2 + 3 + 2 + 4 = 14\).

Computing this directly requires iterating over all divisors of every \(i\). For each \(i\), finding its divisors takes \(O(\sqrt{i})\) time, so the total is \(O(n\sqrt{n})\). Can you do better?

---

Swapping Summation Order — THE Key Technique

The Grid Picture

Think of the double sum \(\sum_{i=1}^{n} \sum_{d \mid i} 1\) as a 2D grid. The rows are indexed by \(i\) (from \(1\) to \(n\)) and the columns by \(d\) (from \(1\) to \(n\)). Place a \(1\) in cell \((i, d)\) whenever \(d \mid i\), and \(0\) otherwise.

For \(n = 6\):

	\(d=1\)	\(d=2\)	\(d=3\)	\(d=4\)	\(d=5\)	\(d=6\)
\(i=1\)	1	0	0	0	0	0
\(i=2\)	1	1	0	0	0	0
\(i=3\)	1	0	1	0	0	0
\(i=4\)	1	1	0	1	0	0
\(i=5\)	1	0	0	0	1	0
\(i=6\)	1	1	1	0	0	1

The original double sum reads this grid row by row: for each \(i\), sum the \(1\)s in its row. That gives \(\tau(i)\), and you add them up.

Now read the same grid column by column. For a fixed \(d\), the \(1\)s appear in rows \(d, 2d, 3d, \ldots\) — every multiple of \(d\) up to \(n\). The number of such multiples is \(\lfloor n/d \rfloor\).

So the column-by-column reading gives:

\[\sum_{d=1}^{n} \lfloor n/d \rfloor\]

Both readings count the same set of \(1\)s in the grid. Therefore:

\[\sum_{i=1}^{n} \sum_{d \mid i} 1 = \sum_{d=1}^{n} \lfloor n/d \rfloor\]

Or equivalently:

\[\boxed{\sum_{i=1}^{n} \tau(i) = \sum_{d=1}^{n} \left\lfloor \frac{n}{d} \right\rfloor}\]

Verify for \(n = 6\): the column sums are \(\lfloor 6/1 \rfloor + \lfloor 6/2 \rfloor + \lfloor 6/3 \rfloor + \lfloor 6/4 \rfloor + \lfloor 6/5 \rfloor + \lfloor 6/6 \rfloor = 6 + 3 + 2 + 1 + 1 + 1 = 14\). Matches.

The General Swap

The same argument works for any function \(f\). The general identity is:

\[\sum_{i=1}^{n} \sum_{d \mid i} f(d) = \sum_{d=1}^{n} f(d) \cdot \left\lfloor \frac{n}{d} \right\rfloor\]

Left side: for each \(i\), sum \(f(d)\) over divisors \(d\) of \(i\).

Right side: for each \(d\), multiply \(f(d)\) by the number of multiples of \(d\) in \([1, n]\), which is \(\lfloor n/d \rfloor\).

These are the same sum, just traversed in different order. Row by row versus column by column. Once you see this, you can't unsee it.

---

Derivation Practice: \(\sum \tau(i)\)

You just saw this, but let's walk through the algebraic steps explicitly, because the mechanical process is what you'll repeat dozens of times in Ch9.

Start with:

\[\sum_{i=1}^{n} \tau(i) = \sum_{i=1}^{n} \sum_{d \mid i} 1\]

Step 1. Rewrite the constraint. The inner sum ranges over \(d\) such that \(d \mid i\). Equivalently, \(i\) is a multiple of \(d\). So the set of pairs \((i, d)\) being summed is \(\{(i, d) : 1 \leq i \leq n, \; d \mid i, \; 1 \leq d \leq i\}\).

Step 2. Swap: instead of fixing \(i\) first (then ranging over \(d \mid i\)), fix \(d\) first (then range over multiples of \(d\) up to \(n\)). The multiples of \(d\) in \([1, n]\) are \(d, 2d, 3d, \ldots, \lfloor n/d \rfloor \cdot d\). There are \(\lfloor n/d \rfloor\) of them.

Step 3. The summand is \(1\) (independent of \(i\)), so each multiple contributes \(1\):

\[= \sum_{d=1}^{n} 1 \cdot \lfloor n/d \rfloor = \sum_{d=1}^{n} \lfloor n/d \rfloor\]

Done. Three steps. This is the template you'll use every time.

---

Another Example: \(\sum \sigma(i)\)

Now apply the same technique to \(\sum_{i=1}^{n} \sigma(i)\).

\[\sum_{i=1}^{n} \sigma(i) = \sum_{i=1}^{n} \sum_{d \mid i} d\]

Here \(f(d) = d\). Apply the swap:

Step 1. Same set of pairs \((i, d)\) with \(d \mid i\) and \(1 \leq i \leq n\).

Step 2. Fix \(d\), range over its \(\lfloor n/d \rfloor\) multiples.

Step 3. Each multiple contributes \(f(d) = d\), so:

\[= \sum_{d=1}^{n} d \cdot \lfloor n/d \rfloor\]

\[\boxed{\sum_{i=1}^{n} \sigma(i) = \sum_{d=1}^{n} d \cdot \left\lfloor \frac{n}{d} \right\rfloor}\]

Verify for \(n = 6\):

Left side: \(\sigma(1) + \sigma(2) + \sigma(3) + \sigma(4) + \sigma(5) + \sigma(6) = 1 + 3 + 4 + 7 + 6 + 12 = 33\).

Right side: \(1 \cdot 6 + 2 \cdot 3 + 3 \cdot 2 + 4 \cdot 1 + 5 \cdot 1 + 6 \cdot 1 = 6 + 6 + 6 + 4 + 5 + 6 = 33\). Matches.

---

Why This Matters: Complexity

The brute-force approach to \(\sum_{i=1}^{n} \tau(i)\) iterates over all divisors of every integer. The total number of divisor pairs \((i, d)\) with \(d \mid i\) and \(i \leq n\) is \(\sum_{d=1}^{n} \lfloor n/d \rfloor \approx n \ln n\). So the brute force is already \(O(n \log n)\) if you enumerate divisors efficiently (by iterating multiples, not trial division).

But the swapped form \(\sum_{d=1}^{n} \lfloor n/d \rfloor\) reveals more structure. Since \(\lfloor n/d \rfloor\) takes only \(O(\sqrt{n})\) distinct values (the floor function is a staircase — this is Ch9 L4), you can group terms with the same floor value and compute the entire sum in \(O(\sqrt{n})\) time. That's a huge speedup for large \(n\).

The swap itself doesn't change the asymptotic cost of the naive loop — both sides iterate over the same pairs. The power is that the swapped form exposes the staircase structure that enables further optimization. The swap is the first step; the staircase trick in L4 is the second step.

---

The Code

Two implementations of \(\sum_{i=1}^{n} \tau(i)\) — brute force (row-by-row) and swapped (column-by-column) — to verify they produce the same answer.

Sum of Tau — Brute Force

long long sumTauBrute(long long limit) {
    long long totalDivisorCount = 0;
    for (long long current = 1; current <= limit; current++) {
        long long divisorCount = 0;
        for (long long candidate = 1; candidate * candidate <= current; candidate++) {
            if (current % candidate == 0) {
                divisorCount++;
                if (candidate != current / candidate) divisorCount++;
            }
        }
        totalDivisorCount += divisorCount;
    }
    return totalDivisorCount;
}

\(O(n\sqrt{n})\) time. For each \(i\), trial division up to \(\sqrt{i}\).

Sum of Tau — Swapped

long long sumTauSwapped(long long limit) {
    long long totalDivisorCount = 0;
    for (long long divisor = 1; divisor <= limit; divisor++) {
        totalDivisorCount += limit / divisor;
    }
    return totalDivisorCount;
}

\(O(n)\) time. One pass, one floor division per step. Already faster than the brute force — and this can be pushed to \(O(\sqrt{n})\) using the staircase technique in L4.

Sum of Sigma — Swapped

long long sumSigmaSwapped(long long limit) {
    long long totalDivisorSum = 0;
    for (long long divisor = 1; divisor <= limit; divisor++) {
        totalDivisorSum += divisor * (limit / divisor);
    }
    return totalDivisorSum;
}

\(O(n)\) time, same structure.

Verification

int main() {
    long long testLimit = 1000;
    cout << "Brute tau sum: " << sumTauBrute(testLimit) << "\n";
    cout << "Swapped tau sum: " << sumTauSwapped(testLimit) << "\n";
    return 0;
}

Run this and confirm both print the same number. For \(n = 1000\), the answer is \(7069\).

---

Common Mistakes

• Forgetting the floor. The count of multiples of \(d\) in \([1, n]\) is \(\lfloor n/d \rfloor\), not \(n/d\). In integer arithmetic (C++ with long long), division truncates automatically, so limit / divisor is correct. But if you're doing pen-and-paper derivations, always write the floor explicitly.

• Off-by-one in the summation range. The swap gives \(\sum_{d=1}^{n}\), not \(\sum_{d=1}^{\sqrt{n}}\) or \(\sum_{d=1}^{n/2}\). Every \(d\) from \(1\) to \(n\) contributes. The upper limit doesn't shrink — it's still \(n\).

• Swapping when the summand depends on both \(i\) AND \(d\). The clean swap \(\sum_{i} \sum_{d \mid i} f(d) = \sum_{d} f(d) \lfloor n/d \rfloor\) works because \(f(d)\) depends only on \(d\), not on \(i\). If your summand is \(g(i, d)\), the swapped form becomes \(\sum_{d=1}^{n} \sum_{k=1}^{\lfloor n/d \rfloor} g(kd, d)\), which may not simplify as neatly. Always check what the summand depends on before swapping.

---

Quick Recap

• \(\sum_{d \mid n} f(d)\) means sum \(f\) over all positive divisors of \(n\). Two key instances: \(f = 1\) gives \(\tau(n)\), \(f = d\) gives \(\sigma(n)\).

• The summation swap identity: \(\sum_{i=1}^{n} \sum_{d \mid i} f(d) = \sum_{d=1}^{n} f(d) \cdot \lfloor n/d \rfloor\). Left reads the divisibility grid row-by-row, right reads it column-by-column.

• The mechanical process: (1) identify the set of pairs, (2) swap which variable you fix first, (3) count multiples.

• The swapped form is often simpler or faster to compute, and exposes the floor staircase structure that enables \(O(\sqrt{n})\) evaluation (Ch9 L4).

• This notation and this swap appear in every remaining lesson of Ch9. Get comfortable with it now.

---

Problems

Problem	Link	Difficulty	Focus
CSES — Sum of Divisors	cses.fi/problemset/task/1082	Medium	Recognize as \(\sum_{d=1}^{n} d \cdot \lfloor n/d \rfloor\); needs staircase trick from L4 for full marks
CSES — Divisor Analysis (sum query)	cses.fi/problemset/task/2182	Medium	Compute \(\sigma\) from prime factorization; reinforces divisor sum definition
CF 1598D — Training Session	codeforces.com/problemset/problem/1598/D	Easy-Medium	Counting divisor pairs; practice reading \(\sum_{d \mid n}\) notation
PE #21 — Amicable Numbers	projecteuler.net/problem=21	Easy	Compute \(\sigma(n)\) for all \(n \leq 10000\); warm-up with divisor sums