35
$\begingroup$

Consider the multiplication table for the numbers $1,2,\dots, n$. How many different numbers are there? That is, how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?

I'm interested in a formula or an algorithm to calculate this number in time less than $O(n^2)$.

$\endgroup$
3
  • 3
    $\begingroup$ A nice paper on this with plenty of references: Multiples and Divisors, by Steven Finch, available online from CiteSeer. $\endgroup$ Jul 13, 2010 at 6:04
  • 2
    $\begingroup$ If all you can hope to save is a fractional power of $\log n$ then you ought to keep track of powers of $\log n$ in the computation model and complexity estimates; and then, even if you use repeated addition rather than multiplication to get each row of the multiplication table, the direct method seems to take $n^2 \log n$ time and space if you count honestly (i.e. $\log n$ bits for a number of size $n$). $\endgroup$ Oct 18, 2013 at 3:58
  • 3
    $\begingroup$ Related: mathoverflow.net/questions/108912/… $\endgroup$ Dec 9, 2013 at 15:49

3 Answers 3

29
$\begingroup$

This is the multiplication table problem of Erdos. According to Kevin Ford, Integers with a divisor in $(y,2y]$, Anatomy of integers, 65-80, CRM Proc. Lecture Notes, 46, Amer Math Soc 2008, MR 2009i:11113, the number of positive integers $n\le x$, which can be written as $n=m_1m_2$, with each $m_i\le\sqrt x$, is bounded above and below by a constant times $x(\log x)^{-\delta}(\log\log x)^{-3/2}$, where $\delta=1-(1+\log\log2)/\log2$.

Erdos' work on this problem can be found (in Russian) in An asymptotic inequality in the theory of numbers, Vestnik Leningrad Univ. Mat. Mekh. i Astr. 13 (1960) 41-49.

Another reference is http://oeis.org/A027424 where a PARI program is given.

$\endgroup$
4
  • 3
    $\begingroup$ Thank you for references! The PARI program implements straightforward $O(n^2)$ algorithm. Is there any algorithm which works faster than $O(n^2)$? $\endgroup$
    – falagar
    Jul 13, 2010 at 8:43
  • 1
    $\begingroup$ Ford's Annals of Mathematics preprint is on the arXiv: arxiv.org/abs/math/0401223 $\endgroup$
    – Charles
    Jul 22, 2010 at 4:35
  • $\begingroup$ @GerryMyerson "the number of positive integers $n\le x$, which can be written as $n=m_1m_2$, with each $m_i\le\sqrt x$, is bounded above and below by a constant times $x(\log x)^{-\delta}(\log\log x)^{-3/2}$, where $\delta=1-(1+\log\log2)/\log2$". That bound is asymptotic bound. Is there a minimum $x$ needed for that bound to be effective? $\endgroup$
    – VS.
    May 5, 2020 at 17:18
  • 1
    $\begingroup$ @VS. I don't know. Have you looked at the paper to see how the bound is expressed there? $\endgroup$ May 5, 2020 at 22:52
12
$\begingroup$

There's a beautiful lecture by Carl Pomerance in which he discusses Erdos's Multiplication Table Problem and then goes on to talk about dense product-free sets of integers. The talk was at the JMM in Boston in 2012. It's available at

https://math.dartmouth.edu/~carlp/sumproductboston.pdf

$\endgroup$
6
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.