36
$\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)$.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ A nice paper on this with plenty of references: Multiples and Divisors, by Steven Finch, available online from CiteSeer. $\endgroup$
    – Sidney Raffer
    Commented 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$
    – Noam D. Elkies
    Commented Oct 18, 2013 at 3:58
  • 3
    $\begingroup$ Related: mathoverflow.net/questions/108912/… $\endgroup$
    – Eric Naslund
    Commented Dec 9, 2013 at 15:49

3 Answers 3

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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.
    Commented 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$
    – Gerry Myerson
    Commented 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

Improve this answer
$\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}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .