MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider multiplication table for numbers $1,2,\cdots, 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 formulae or an algorithm to calculate this number in time less than $O(n^2)$.

share|cite|improve this question
A nice paper on this with plenty of references: Multiples and Divisors, by Steven Finch, available online from CiteSeer. – SJR Jul 13 '10 at 6:04
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$). – Noam D. Elkies Oct 18 '13 at 3:58
Related:… – Eric Naslund Dec 9 '13 at 15:49

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 where a PARI program is given.

share|cite|improve this answer
Thank you for references! The PARI program implements straightforward $O(n^2)$ algorithm. Is there any algorithm which works faster than $O(n^2)$? – falagar Jul 13 '10 at 8:43
Ford's Annals of Mathematics preprint is on the arXiv: – Charles Jul 22 '10 at 4:35

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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