Algorithms for the Multiplication Table Problem

Abstract

Let $M(n)$ denote the number of distinct entries in the $n\times n$ multiplication table. The function $M(n)$ has been studied by Erdős, Tenenbaum, Ford, and others, but the asymptotic behaviour of $M(n)$ as $n\to \infty$ 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^{30}$, 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.

15 pages, 3 tables, small improvements and references added in v2

References in corpus (1)

• Improved error bounds for the Fermat primality test on random inputs