Algorithms for the Multiplication Table Problem

Let M(n) denote the number of distinct entries in the n×n multiplication table. The function M(n) has been studied by Erdős, Tenenbaum, Ford, and others, but the asymptotic behavior of M(n) as n → ∞ is not known precisely. Thus, there is some interest in algorithms for computing M(n) either exactly or approximately. We compare several algorithms for computing M(n) exactly, and give a new algorithm that has a subquadratic running time. We also present two Monte Carlo algorithms for approximate computation of M(n). We give the results of exact computations for values of n up to 2³⁰, and of Monte Carlo computations for n up to 2^100,000,000, and compare our experimental results with Ford’s order-of-magnitude result.