Counting ordered triples whose product is at most $n$

Question

There is a classical question in discrete math such a kind that

Let $a\times b \times c =24 $ then , how many possible $(a,b,c)$ triples are there where $a,b,c \in Z^+$

The answer is the following $x_1+x_2+x_3 =3$ and $y_1+y_2+y_3 =1$ , then $$\binom{3+3-1}{3}\binom{3+1-1}{1}=30$$

Now , i want to turn this question to this one such that

Let $a\times b \times c < 24 $ then , how many possible $(a,b,c)$ triples are there where $a,b,c \in Z^+$

In first hand , it thought to add another integer $d$ such that $d >1 $ and $a\times b \times c \times d = 24 $

Now , i must do the same calculation like in triple case and subtract the cases where $d=1$ from the total.For example , $$\binom{4+3-1}{2}\binom{4+1-1}{1}-\binom{3+3-1}{3}\binom{3+1-1}{1}=60-30 =30$$

However , my logic is wrong ,i saw it for small case such as $a \times b \times c =6$.

Do you have any suggestion or solution for my problem except for computer programming ?

B.T.W My question is not only specific for $24$ , i chose it because it is easy to handle , but it could be any other number such as $678$ etc. So , i am looking for the solution which can handle large numbers

Answer 1

Let $f_3(n)$ be the number of positive integer solutions to $$ a\times b\times c\le n $$ We can compute $f_3(n)$ in approximately $O(n^{5/6})$ time.

First, let us define $f_2(n)$ to be the number of solutions to $a\times b\le n$, as this will be useful for computing $f_3(n)$. Note that for any pair $(a,b)$ such that $a\times b\le n$, we will have $$ \text{either $a\le \lfloor n^{1/2}\rfloor $ or $b\le \lfloor n^{1/2}\rfloor $} $$ Therefore, using the principle of inclusion exclusion, $$ \begin{align} f_2(n) &=\phantom{ + }\#\{\text{pairs where $a\le \lfloor n^{1/2}\rfloor $}\} \\ &\phantom{ = }+\#\{\text{pairs where $b\le \lfloor n^{1/2}\rfloor $}\} \\ &\phantom{ = }-\#\{\text{pairs where $a\le \lfloor n^{1/2}\rfloor $ and $b\le \lfloor n^{1/2}\rfloor $}\} \end{align} $$ Conclude as follows: $$ \begin{align} \#\{\text{pairs where $a\le \lfloor \sqrt n\rfloor $}\} &=\sum_{a=1}^{\lfloor n^{1/2}\rfloor} \lfloor n/a\rfloor\\ \#\{\text{pairs where $a\le \lfloor \sqrt n\rfloor $ and $b\le \lfloor \sqrt n\rfloor $}\} &=(\lfloor n^{1/2}\rfloor )^2 \end{align} $$ Using these formulae, computing $f_2(n)$ takes $O(n^{1/2})$ time, ignoring the cost of arithmetic operations.

Now, let us leverage this to compute $f_3(n)$. Let $E_a$ be the set of triples $(a,b,c)$ such that $a\times b\times c\le n$, and for which $a\le \lfloor n^{1/3}\rfloor$. Define $E_b$ and $E_c$ similalry. Using PIE again, $$ f_3(n)=|E_a|+|E_b|+|E_c|-|E_a\cap E_b|-|E_a\cap E_c|-|E_b\cap E_c|+|E_a\cap E_b\cap E_c| \\ \hspace{-5.65cm}=3|E_a|-3|E_a\cap E_b|+|E_a\cap E_b\cap E_c| $$ Finally, conclude by noting \begin{align} |E_a|&=\sum_{a=1}^{\lfloor n^{1/3}\rfloor }f_2(\lfloor n/a\rfloor ) \\ |E_a\cap E_b|&= \sum_{a=1}^{\lfloor n^{1/3}\rfloor} \sum_{b=1}^{\lfloor n^{1/3}\rfloor}\lfloor n/(ab)\rfloor \\ |E_a\cap E_b\cap E_c|&=(\lfloor n^{1/3}\rfloor )^3 \end{align}

Answer 2

The original function is known as $\tau_3(n)$. The sequence is in the OEIS as A007425. Your question about the number of ordered triples $(a,b,c)$ with $abc < 24$ is $\sum_{i=1}^{23} \tau_3(n)$.

Those partial sums are A061201 which includes a nice formula given by Wesley Ivan Hurt using the integer floor function: $$a(n) = \sum_{k=1}^n \sum_{i=1}^n \left\lfloor\frac{n}{ik}\right\rfloor.$$ The derivation is probably along the lines of Mike Earnest's answer. That formula is for partial sums including $\tau_3(n)$, so the answer to your question for 24 is $a(23) = 173$.

Answer 3

This solution is only intended for the problem specified in the title. And this is not the full solution.

We have $$a×b×c<24$$ Consider the case where $a=b=c$

Triplets here formed will be only $$(1,1,1) \:\:(2,2,2)$$

Now consider the case $a=b\ne c$

Triplets formed here will be $$(1,1,2)\:\:(1,1,3)\cdots(1,1,23)$$ $$(2,2,1)\:\:(2,2,3)\:\:(2,2,4)\:\:(2,2,5)$$ $$(3,3,1)\:\:(3,3,2)$$ $$(4,4,1)$$ Cases $a=c\ne b$ and $b=c\ne a$ will have same number of cases as above

So till now we got $$2+29×3=89 \:\:\textrm{cases}$$ Now the case left is $a\ne b\ne c$

And I'm working on that...