The Multiplication Table Median

Take a $61 \times 61$ multiplication table. It has $3721$ entries. What is the median — the 1861st value when all entries are sorted?

Most people guess somewhere near $1800$ — roughly half of $3721$, the maximum entry.

The actual median is $\mathbf{779}$.

Less than a quarter of the way up the range. Why?

---

Setting up the question

The entries of an $n \times n$ multiplication table are the products $\{i \cdot j : 1 \leq i, j \leq n\}$.

There are $n^2$ entries in total (with repetitions). The median is the value $M$ such that exactly half the entries satisfy $i \cdot j \leq M$.

So we need: how many pairs $(i, j)$ with $1 \leq i, j \leq n$ satisfy $ij \leq M$?

Call this count $f(M)$. We want the smallest $M$ such that $f(M) \geq n^2/2$.

---

The count is a lattice point problem

$f(M)$ is the number of lattice points $(i, j)$ with $1 \leq i, j \leq n$ and $ij \leq M$.

For $M \leq n^2$, this is the number of integer pairs inside the rectangle $[1,n] \times [1,n]$ that also lie below the hyperbola $y = M/x$.

$f(M) = \sum_{i=1}^{n} \min\!\left(n,\ \left\lfloor \frac{M}{i} \right\rfloor\right)$

For small $i$ (where $M/i > n$), the constraint is just $j \leq n$ — all $n$ values work. For large $i$ (where $M/i < n$), the constraint is $j \leq M/i$.

The crossover happens at $i = M/n$.

---

Why the median is small

The hyperbola $ij = M$ is dense near the axes. When $i$ is small, $j$ can be as large as $M/i$ — many pairs. When $i$ is large, $j$ is forced small.

The "density" of lattice points is not uniform across the rectangle. It clusters near the edges where one coordinate is small.

Because of this clustering, you reach half the table's entries at a value $M$ far below $n^2/2$.

Rough estimate. The total number of pairs with $ij \leq M$ is approximately (from the hyperbola area):

$f(M) \approx M\ln\!\left(\frac{n^2}{M}\right) + \text{lower order}$

Setting $f(M) = n^2/2$ and solving gives $M \approx n^2 / (2\ln n)$ roughly — much smaller than $n^2/2$.

For $n = 61$: $n^2 = 3721$, $\ln 61 \approx 4.11$, giving $M \approx 3721/8.22 \approx 453$. The true answer 779 is in the right ballpark — the rough estimate is off because the formula needs more terms, but the order of magnitude is correct.

---

The exact computation

To find the exact median for a given $n$:

1. For each candidate $M$, compute $f(M) = \sum_{i=1}^{n} \min(n, \lfloor M/i \rfloor)$.
2. Binary search on $M$ in $[1, n^2]$ until $f(M) \geq n^2/2$ and $f(M-1) < n^2/2$.

The binary search takes $O(\log n^2) = O(\log n)$ steps. Each evaluation of $f(M)$ takes $O(n)$ steps. Total: $O(n \log n)$.

For $n = 61$, this is fast. For large $n$, the hyperbola-splitting trick from Counting Lattice Points reduces each evaluation to $O(\sqrt{M})$.

---

What this reveals about multiplication tables

The median being at $\sim n^2 / (c \log n)$ rather than $n^2/2$ has a concrete interpretation:

Most products in the table are small. The multiplication table is not a uniform sample from $[1, n^2]$. Numbers near 1 are overrepresented (many pairs $(i, j)$ give small products), while numbers near $n^2$ are underrepresented (only the pair $(n, n)$ gives the maximum).

This is the same skewness that makes the average number of divisors grow like $\ln n$ — both come from the hyperbola's shape.

---

Worked problems

Problem 1. In a $10 \times 10$ multiplication table, how many entries are $\leq 20$?

Count pairs $(i,j)$ with $1 \leq i,j \leq 10$ and $ij \leq 20$:

For each $i$: $j \leq \min(10, \lfloor 20/i \rfloor)$.

$i$	$\lfloor 20/i \rfloor$	$\min(10, \cdot)$
1	20	10
2	10	10
3	6	6
4	5	5
5	4	4
6	3	3
7	2	2
8	2	2
9	2	2
10	2	2

Total: $10+10+6+5+4+3+2+2+2+2 = 46$.

So 46 out of 100 entries are $\leq 20$. The median is slightly above 20.

Problem 2. Estimate the median of a $100 \times 100$ multiplication table.

$n=100$, $n^2 = 10000$. Rough estimate: $M \approx n^2/(2\ln n) = 10000/(2 \times 4.605) \approx 1086$.

The true median is around 1369. Again the estimate captures the right scale — much less than 5000.

Problem 3. Prove that at least $n$ distinct values appear in an $n \times n$ multiplication table.

The entries $1\times 1, 1\times 2, \ldots, 1\times n$ are $n$ distinct values: $1, 2, \ldots, n$. $\blacksquare$

(The actual number of distinct values is much larger — a result of Erdős and others.)

---

The full asymptotic expansion of $D(n) = \sum_{k=1}^n \tau(k)$ — which underlies all of this — is the content of Dirichlet's Divisor Problem.