TheThis is a well-known problem and is acquiring a cardinality ofabout counting the setnumber of distinct numbers in the $n \times n$ multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further input on it by itself. There has been, however, a significant amount of debate about it on StackOverflow, namely this question:
and this question/bounty:
As far as I understand, the problem has currently only O(n^2)$O(n^2)$ computational solutions (strictly speaking, k*n^2$kn^2$ iterations, with k=0.5$k=0.5$), while the asymptotic size of the set is equal to $$\left|\lbrace a\cdot b:\ a,b\leq N\rbrace\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$ (Ford, 2008).
As far as my knowledge goes, there is no explicit way to generate a set of size A(n)$A(n)$ and to calculate it'sits cardinality without at least A(n)$A(n)$ operations. Also, there currently exists no solution to acquiringdetermine the exact value of A(n)$A(n)$ without generating the set and counting its unique elements.
There has been significant amount of dispute about it by certain individuals, convinced there is an O(n)$O(n)$ solution to the problem [calculating A(n)$A(n)$], and that they have found it. Although such solutions are usually disproven, I'm interested if it's at all possible for this problem to be solved strictly below O(n^2)$O(n^2)$, either with explicitly generating the set or using some functional relationship between n$n$ and A(n)$A(n)$. Currently, both the reference solutions and the one sent by David are O(n^2)$O(n^2)$.
[edit] forEdit. For clarity, let us split this into two questions: a) can exact A(n) for a specific n be actually calculated without generating the set itself (i.e. without any need to know and possibly without any method to tell if a number is in the set, or not) - and if so, how? If not, possible reasons for practical/theoretical possibility/impossibility of creating such solution would be perfect, b) can A(n) be computed by generating the set in strictly below O(n^2) complexity (e.g. O(n^2/log log N) or similar)? If so, how would that be possible?
a) Can exact $A(n)$ for a specific $n$ be actually calculated without generating the set itself (i.e. without any need to know and possibly without any method to tell if a number is in the set, or not) and if so, how? If not, possible reasons for practical/theoretical possibility/impossibility of creating such solution would be perfect.
b) Can $A(n)$ be computed by generating the set in strictly below $O(n^2)$ complexity (e.g. $O(n^2/\log \log n)$ or similar)? If so, how would that be possible?
related:
How many different numbers can be obtained as product of first $n$ natural numbers?
Distinct numbers in multiplication table
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
