26
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ A nice paper on this with plenty of references: Multiples and Divisors, by Steven Finch, available online from CiteSeer. $\endgroup$ – Sidney Raffer Jul 13 '10 at 6:04
  • 1
    $\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 Oct 18 '13 at 3:58
  • 2
    $\begingroup$ Related: mathoverflow.net/questions/108912/… $\endgroup$ – Eric Naslund Dec 9 '13 at 15:49
27
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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 '10 at 8:43
  • 1
    $\begingroup$ Ford's Annals of Mathematics preprint is on the arXiv: arxiv.org/abs/math/0401223 $\endgroup$ – Charles Jul 22 '10 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 at 17:18
  • $\begingroup$ @VS. I don't know. Have you looked at the paper to see how the bound is expressed there? $\endgroup$ – Gerry Myerson May 5 at 22:52
9
$\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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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