How many tuples of {$a, b, c, ...$} satisfy $abc... \leq n$?

314 Views Asked by At

Let $n$ and $k$ be positive integers.

Let $a, b, c, ...$ be $k$ positive integers such that $abc... \leq n$.

How many tuples of {$a, b, c, ...$} satisfy the inequality?

Note that the tuples {$a=1, b=2$} and {$a=2, b=1$} are two different tuples.

For $k = 1$, the answer is $n$.

So for $k = 2$, the answer is $\sum_{i=1}^n floor(\frac{n}{i})$ also $\sum_{i=1}^n d(i)$, where $d$ = number of divisors. http://oeis.org/A006218

2

There are 2 best solutions below

2
On

Even for $k=2$ this is a hard problem; the first few terms (for $n=1\ldots 10$) would be $$ \{ 1,3,5,8,10,14,16,20,23,27\} $$ While no closed form exists in terms of familiar functions, the large-$n$ behavior is a well-studied problem (the Dirichlet divisor problem) with the result that it goes like $$ n(\log n + 2 \gamma -1) + O(\sqrt{n}) $$

0
On

Let's consider the case in which the product is equal to $q$.
If $q$ has the prime factorization $$ q = p_{\,1} ^{\,k_{\,1} } p_{\,2} ^{\,k_{\,2} } \cdots p_{\,h} ^{\,k_{\,h} } $$ then a divisor $a_j$ of $q$ shall have a prime factorization where each exponent ($x_{j,l}$) is not greater than the corresponding exponent of $p_l$ for $q$.

So we have that $$ a_{\,1} a_{\,2} \cdots a_{\,m} = q\quad \Rightarrow \quad \left\{ \matrix{ 0 \le x_{\,u,v} \in Z \hfill \cr x_{\,1,1} + x_{\,1,2} + \cdots + x_{\,1,m} = k_{\,1} \hfill \cr x_{\,2,1} + x_{\,2,2} + \cdots + x_{\,2,m} = k_{\,2} \hfill \cr \quad \quad \vdots \hfill \cr x_{\,h,1} + x_{\,h,2} + \cdots + x_{\,h,m} = k_{\,h} \hfill \cr} \right. $$

The number of solutions to each line is the number of [weak compositions][1] of $k_j$ into $m$ parts, i.e. $$ \left( \matrix{ k_{\,j} + m - 1 \cr m - 1 \cr} \right) $$

I do not see how we can formulate the product of the binomials above in a compact way.