Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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
2  
Related: mathoverflow.net/questions/108912/… –  Eric Naslund Dec 9 '13 at 15:49
add comment

1 Answer 1

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.

share|improve this answer
2  
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: arxiv.org/abs/math/0401223 –  Charles Jul 22 '10 at 4:35
add comment

Your Answer

 
discard

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.