Detailed mathematical approach

Problem Summary

Define

$P(m,n)=\#\{ab:1\le a\le m,\ 1\le b\le n\},$

the number of distinct values appearing in the \(m\times n\) multiplication table. The goal is to compute \(P(m,n)\) for very large \(n\) without generating all \(mn\) products. The checked implementations use the published values

$P(64,64)=1263,\qquad P(12,345)=1998,\qquad P(32,10^{15})=13826382602124302.$

Mathematical Approach

The key idea is to assign every distinct product to exactly one row, then count how many column indices survive in that row after excluding all products that also belong to a larger row.

Step 1: Assign Each Product to a Unique Owner Row

Take any product \(x\) that appears in the table, so \(x=ab\) for some \(1\le a\le m\) and \(1\le b\le n\). Let \(d\) be the largest divisor of \(x\) with \(d\le m\). Then \(x=d\,c\) for some integer \(c\), and because \(d\ge a\), we get

$c=\frac{x}{d}\le \frac{x}{a}=b\le n.$

So \(x\) still appears in row \(d\), and by construction no larger row index up to \(m\) divides it. This makes the owner row unique.

Let \(C_d\) be the number of column values \(c\in[1,n]\) such that \(x=d\,c\) is owned by row \(d\). Then

$P(m,n)=\sum_{d=1}^{m} C_d.$

Step 2: Translate Higher Rows into Divisibility Constraints on the Column

Fix a row \(d\). A larger row \(e>d\) steals the product \(d\,c\) exactly when \(e\mid d\,c\). Write

$g=\gcd(e,d),\qquad e=g\,e',\qquad d=g\,d',$

with \(\gcd(e',d')=1\). Then

$e\mid d\,c \iff g\,e' \mid g\,d'\,c \iff e' \mid d'\,c \iff e' \mid c,$

because \(e'\) is coprime to \(d'\). Therefore the higher row \(e\) forbids exactly the columns divisible by

$q_{e,d}=\frac{e}{\gcd(e,d)}.$

If \(q_{e,d}>n\), it can be ignored, since no positive \(c\le n\) is divisible by it.

Step 3: Keep Only the Minimal Forbidden Divisors

For a fixed \(d\), consider all values \(q_{e,d}\) with \(d<e\le m\). Duplicates do not matter. More importantly, if one forbidden divisor is a multiple of another, the larger one is redundant: whenever \(q_2\) is a multiple of \(q_1\), every \(c\) divisible by \(q_2\) is already divisible by \(q_1\).

So we keep only a minimal set under divisibility:

$Q_d=\{q_1,q_2,\dots,q_t\}.$

Now \(C_d\) is simply the number of integers \(c\le n\) that are not divisible by any element of \(Q_d\).

Step 4: Count the Surviving Columns by Inclusion-Exclusion

For any subset \(S\subseteq Q_d\), the integers \(c\le n\) divisible by every element of \(S\) are exactly the multiples of \(\operatorname{lcm}(S)\). Hence

$C_d=\sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor,$

with the convention \(\operatorname{lcm}(\emptyset)=1\). Written out, this is

$C_d=n-\sum_i\left\lfloor\frac{n}{q_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{\operatorname{lcm}(q_i,q_j)}\right\rfloor-\cdots.$

Combining this with the row decomposition gives the final formula

$\boxed{P(m,n)=\sum_{d=1}^{m}\ \sum_{S\subseteq Q_d}(-1)^{|S|}\left\lfloor\frac{n}{\operatorname{lcm}(S)}\right\rfloor.}$

Step 5: Worked Example \(P(3,4)=8\)

For \(d=1\), the higher rows are \(2\) and \(3\), so the forbidden divisors are \(2\) and \(3\). Thus

$C_1=4-\left\lfloor\frac{4}{2}\right\rfloor-\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{4}{6}\right\rfloor=4-2-1+0=1.$

For \(d=2\), only row \(3\) is higher, and it forbids multiples of \(3\). Hence

$C_2=4-\left\lfloor\frac{4}{3}\right\rfloor=3.$

For \(d=3\), there is no higher row, so \(Q_3=\emptyset\) and \(C_3=4\).

Therefore

$P(3,4)=C_1+C_2+C_3=1+3+4=8.$

The eight distinct products are \(\{1,2,3,4,6,8,9,12\}\).

How the Code Works

The C++, Python, and Java implementations all follow the same row-by-row counting strategy. For each row \(d\), the implementation generates the values \(e/\gcd(e,d)\) for all larger rows \(e\), discards values greater than \(n\), removes duplicates, and then removes any value that is a multiple of an already kept smaller divisor.

After that reduction, the implementation performs recursive inclusion-exclusion over the remaining forbidden divisors. At each recursive step it updates the running least common multiple using a gcd-based formula, and it immediately prunes the branch if the lcm would exceed \(n\) or overflow the allowed bound. The row counts are then summed to obtain \(P(m,n)\).

The C++ version also takes advantage of the fact that different rows are independent, so it can evaluate row contributions in parallel. The checked code further validates the method against the published checkpoints above and against small direct enumerations.

Complexity Analysis

Let \(t_d=|Q_d|\). Building the raw forbidden list for row \(d\) takes \(O(m-d)\) gcd computations, followed by sorting and duplicate removal. The minimal-divisor filtering is quadratic in the size of that provisional list in the worst case, but \(m\) is small in the actual problem.

The inclusion-exclusion stage depends on how many subset lcms remain at most \(n\). In the worst case it is \(O(2^{t_d})\) for row \(d\), but the minimal-divisor reduction and the lcm cutoff prune many branches in practice. Overall, the method is dramatically smaller than generating all \(mn\) products, and its memory usage is modest: essentially one row's forbidden-divisor list plus the recursion stack.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=466
2. Multiplication table: Wikipedia — Multiplication table
3. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
4. Greatest common divisor: Wikipedia — Greatest common divisor
5. Least common multiple: Wikipedia — Least common multiple