How many unique numbers can be obtained from multiplying two natural numbers less than $N$?

Solution 1:

This is a fairly hard problem, and one that at the very least is not solvable by methods from elementary combinatorics. It's sometimes referred to as Erdős' multiplication table.

For counting the exact number, OEIS A027424 gives several algorithms which compute the number of unique products $M(n)$ in the $n \times n$ multiplication table, but they all rely on computing the entire multiplication table and then counting the number of unique values. Hence their complexity is $\Theta(n^2)$, and it isn't really clear whether there's an algorithm that's much faster than that. See e.g. this question here and this one on MathOverflow.

The asymptotics of $M(n)$ are fairly well established. Erdős proved in 1955 that $M(n) = o(n^2)$, and Ford proved in 2008 arXiv link that (from this answer on Mathoverflow) $$ M(n) \asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}. $$