# Counting ordered triples whose product is at most $n$

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

• I hope you mean ordered triplets Nov 22, 2022 at 21:14
• The problem with your solution is that, for example, you want to include solutions to $a \times b \times c = 17$ (or any other number that is less than 24 but does not divide 24) and for such triples there will not be any choice of integer $d$ such that $a \times b \times c \times d = 24$.
– JBL
Nov 23, 2022 at 3:05

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}

• What havs you actually written $?$ i cant understand even a single thing!!! Can you pls explain$?$ Nov 23, 2022 at 9:55

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$$.

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...