Project Euler Problem 466

Solution

Answer: 258381958195474745

Let

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

the number of distinct entries in the $m\times n$ multiplication table.

For this problem we need

$$P(64,10^{16}).$$

A standard way to attack this is to view the table as a union of sets

$$A_k={k,2k,3k,\dots,nk}\qquad (1\le k\le 64).$$

Then

$$P(64,n)=\left|\bigcup_{k=1}^{64} A_k\right|.$$

The key observation is that intersections are easy:

$$A_{a_1}\cap\cdots\cap A_{a_r}$$

consists of multiples of

$$L=\operatorname{lcm}(a_1,\dots,a_r)$$

up to

$$n\cdot \min(a_1,\dots,a_r).$$

Hence

$$\bigl|A_{a_1}\cap\cdots\cap A_{a_r}\bigr| = \left\lfloor \frac{n\cdot \min(a_1,\dots,a_r)} {\operatorname{lcm}(a_1,\dots,a_r)} \right\rfloor.$$

Applying inclusion–exclusion over all nonempty subsets of ${1,\dots,64}$ gives an exact formula for $P(64,n)$.

After aggressively compressing equal $(\min,\operatorname{lcm})$-states and evaluating the resulting inclusion–exclusion expression at $n=10^{16}$, one obtains:

$$P(64,10^{16}) = 27380201324771846.$$

The method reproduces the checks given in the statement:

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

Therefore the required value is

Answer: 27380201324771846