Algorithms for the Multiplication Table Problem

We present several algorithms for computing $M(n)$, the function that counts the number of distinct products in an $n\times n$ multiplication table. In particular, we consider their run-times and space bounds for single evaluation, tabulation, and Monte-Carlo estimation. We give the result of exact computations up to $n = 2^{30}-1$ and Monte Carlo computations for larger $n$.