The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either.
We have two integer numbers $1 < a,b < N$, how many unique products of $a \cdot b$ there are? The possible simplification could be that $N$ is also a prime, as I also interested in a good estimation. My more basic question is it less than $O(N^2)$, but the actual count seems more interesting.
This seems related to How many unique combination of $n$ numbers are there when multiplying $x$ numbers?, though answerer there makes one assumption which is a killer IMO, all the products are distinct ("unless they have to" which, I believe, meant commutativity of multiplication). In the above the statement is clearly false. E.g. $1 \cdot 4 = 2 \cdot 2$ or $4 \cdot 4 = 2 \cdot 8$. $24$ would also appear quite some times.
What have I tried:
The obvious upperbound is $N^2$ which is a clear over-estimation (even if we divide it by 2 due to commutitativity) – we cannot obtain any compound involving prime $p_i$ such as $N < p_i < N^2$.
My approach was to count prime numbers and assume all the possible numbers are compounds of them, the answer from the cited question could be used then, but this is also not true. E.g. for $N=5$ we need to treat $4$ as a (pseudo) prime to get $20$.
I can't figure how to count numbers to be excluded from $N^2$, or which to include and when. I had idea that all numbers greater than $\sqrt{N}$ (or maybe $N/2$) can be treated as those pseudo-primes, but I am not sure if this is the correct way.
Best Answer
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}. $$