most recent 30 from http://mathoverflow.net 2013-05-25T05:04:41Z http://mathoverflow.net/feeds/question/31663 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table falagar 2010-07-13T05:37:54Z 2010-07-13T06:06:21Z

<p>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?</p> <p>I'm interested in a formulae or an algorithm to calculate this number in time less than $O(n^2)$.</p>

http://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table/31666#31666 Gerry Myerson 2010-07-13T06:00:21Z 2010-07-13T06:06:21Z

<p>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$. </p> <p>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. </p> <p>Another reference is <a href="http://www.research.att.com/~njas/sequences/A027424" rel="nofollow">http://www.research.att.com/~njas/sequences/A027424</a> where a PARI program is given. </p>