Skip to main content
5 of 7
added 540 characters in body
Hujdurovic
  • 323
  • 2
  • 6

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set

$\{1^{a_1} \cdot 2^{a_2} \cdot \ldots \cdot n^{a_n}\mid a_i\geq 0, a_1+a_2+\ldots+a_n=m \}$.

How many results can be obtained?

Denote this number with $P(m,n)$ (the number of elements of the set defined above). For example, if $m=1$, then $P(1,n)=n$. Similarly, we have:

$P(m,1)=1$,

$P(m,2)=m+1$.

Moreover, if $n=p$ is prime then it is not difficult to see that $$P(m,p)=\sum_{i=0}^{m}P(i,p-1).$$ (We define $P(0,n)$ to be equal $1$ for any $n$.)

Furhter, using the above property one can obtain the values of $P(m,n)$, for some small values of $n$, for example for $n\leq 10$ we have:

$P(m,3)=\binom{m+2}{2}$;

$P(m,4)=(m+1)^2$;

$P(m,5)=\frac{(m+1)(m+2)(2m+3)}{6}$

$P(m,6)=(m+1){{m+2}\choose{2}}$;

$P(m,7)=\frac{(m+1)(m+2)(m+3)(3m+4)}{24}$;

$P(m,8)=\frac{(m+1)^2(m+2)(m+3)}{6}$;

$P(m,9)=\frac{(m+1)^2(m+2)^2}{4}$;

$P(m,10)=\frac{(m+1)^2(m+2)(2m+3)}{6}$.

Is there a general method that would give precise value of $P(m,n)$ for any $m$ and $n$? Or at least an approximation of $P(m,n)$?

Hujdurovic
  • 323
  • 2
  • 6