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

  • $\begingroup$ 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. $\endgroup$ – Mark Fischler May 23 at 19:35
  • $\begingroup$ @Mark Fischler: Thanks. I corrected it. $\endgroup$ – 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}) $$

  • $\begingroup$ What is $20.23.27$? $\endgroup$ – manooooh May 23 at 20:18
  • 1
    $\begingroup$ Ooops!It is $$\lim_{,\to .} 20,23,27$$ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.