Counting Products

Consider the set $S$ of all possible products of $n$ positive integers not exceeding $m$, that is
$S=\{ x_1x_2\cdots x_n \mid 1 \le x_1, x_2, \dots, x_n \le m \}$.

Let $F(m,n)$ be the number of the distinct elements of the set $S$.
For example, $F(9, 2) = 36$ and $F(30,2)=308$.
Find $F(30, 10001) \bmod 1\,000\,000\,007$.

This problem can be addressed by number theory. Significant understanding of number theory is required with a strong concept and understanding of the function $F(m,n)$.

As a start, for $F(m,n)$, it basically counts all distinct products of $n$ numbers where each of these numbers is from $1$ to $m$. To understand it more systematically, first we need to convert the product into summation which is why a simplification of this kind is needed: $log(x_1 * x_2 * … * x_n) = log(x_1) + log(x_2) + … + log(x_n)$.

Use logs to the base m. Since $1\leq x\leq m$, $0\leq \log(x)\leq 1$.

The summation indicates that we are trying to partition $n$ into some parts where each part is within $[0,1]$. And we need to find the possible distinct results which may be $n$, $n-1+{1\over m}$, $n-2+{2\over m}$, …, $1+(n-1)/m$. So the number should be $F(m,n) = n\cdot m-(m-1) = m(n-m+1)$.

To find $F(m,n)$ where $n>m$, apply the same method to partition $n$ into $m$ parts where each part is within $[1,m]$. The possible results count should be $F(m,n)= {n-1\choose m-1}$.

However, these results only count distinct real numbers but not integers which we care about. Bear in mind that $F(1,n)$ are integers, so let’s begin from there.

$F(1,n)=1$.

For $F(2,n)$, we have $F(2,n) = 2(2-2+1) = 2$ if $n<2$ and $F(2,n)={n-1\choose 2-1}=n$ if $n>=2$, it’s easy to check that the result is in line with reality.

For $F(3,n)$, the partition strategy is like looking at the number of partitions of $n-3i$ into $n-i$ parts for some $i$ within $[0,n/3]$. So the result should be $\sum_{i=0}^{n/3} {n-i-1 \choose n-2i-1}$.

Utilizing this strategy, for $m>3$, $F(m,n)$ is the summation of multiple binomial coefficients related to $F(m-1,n)$ and so on.

However, here comes the final challenge: to give $F(30,10001)$ under modulo $1,000,000,007$. The complexity of the problem is beyond simple calculation and needs the application of Lucas’ Theorem and FFT(Fast Fourier Transform) to handle it within a reasonable time frame.

What’s mentioned above is a general and systematic guide of the problem-solving, which provides you with the understanding of the problem from a theoretical perspective.

More Answers: