## Distinct numbers in multiplication table

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

2
A nice paper on this with plenty of references: Multiples and Divisors, by Steven Finch, available online from CiteSeer. – SJR Jul 13 2010 at 6:04

## 1 Answer

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://www.research.att.com/~njas/sequences/A027424 where a PARI program is given.

-

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 2010 at 8:43
Ford's Annals of Mathematics preprint is on the arXiv: arxiv.org/abs/math/0401223 – Charles Jul 22 2010 at 4:35
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8408623337745667, "perplexity_flag": "middle"}