Return to Revisions

Regarding the algorithmic question, a recent paper of Brent, Pomerance, Purdum, and Webster presents a subquadratic algorithm to compute the number of distinct products $M(n)$ of the $n \times n$ multiplication table. They have implemented their results to compute $M(n)$ exactly for all $n \leq 2^{30}$. They note that for larger values of $n$, exact algorithms become impractical, and so the paper also presents two Monte Carlo algorithms to approximate $M(n)$. Monte Carlo computations are presented for $n$ up to $2^{100000000}$.