Skip to main content
10 of 10
edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Erdős multiplication problem revisited

This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.

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:

https://stackoverflow.com/questions/24614798/find-the-number-of-distinct-numbers-in-multiplication-table

As far as I understand, the problem has currently only $O(n^2)$ computational solutions (strictly speaking, $kn^2$ iterations, with $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)$ and to calculate its cardinality without at least $A(n)$ operations. Also, there currently exists no solution to determine the exact value of $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)$ solution to the problem [calculating $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)$, either with explicitly generating the set or using some functional relationship between $n$ and $A(n)$. Currently, both the reference solutions and the one sent by David are $O(n^2)$.

Edit. 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?

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\}$

user56218