How many different products can we get using the first n natural number?

Question

Let $U=\{1,2,3,...,n\}$ and $s$ to be an non-empty subset of $U$, let $prod$ be a function on set to calculate the product of all elements in a set.

My question is, what is the number of elements in $\{prod(s)\}$.

For example, if $n=4$, then there is $\{1,2,3,4,6,8,12,24\}$.

Note that the answer isn't just the number of factors of $n!$.

It confused me a lot. Could anyone help me with it

Answer 1

There is no simple formula known for this difficult problem.

Consider $A(n,k)$ the number of products of $k$ elements from $\{1,2,\ldots,n\}.$ For $k=2,$ this is the famous Erdos Multiplication Table problem. Your question is essentially the size of the union of the sets $A(n,k),$ for $1\leq k\leq \sqrt{n}.$

The best known general result for $k=2$ is a recent asymptotic estimate (for $x$ large) due to Ford:

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

To translate to your question take $x=n^2,$ which would give $$O\left(\frac{n}{(2\log n)^{\delta}(\log(2 \log n))^{3/2}}\right),$$ as the number of 2-way products.

For $k\leq 5,$ there are estimates known, but that's it. The same question and its answers has some discussion concerning algorithms to compute this quantity for fixed $k.$

See this question on mathoverflow for more.