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

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

• Well, for $k=2$, apply $n=5$ to your conjectured answer to see that it makes little sense -- there can't be 12.5 such tuples. – Mark Fischler May 23 at 19:35
• @Mark Fischler: Thanks. I corrected it. – Omega Force May 23 at 19:52

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

• What is $20.23.27$? – manooooh May 23 at 20:18
• Ooops!It is $$\lim_{,\to .} 20,23,27$$ – Mark Fischler May 23 at 20:34

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.