# find the number of possible positive integer solutions when the inequality is $a \times b \times c \lt 180$

As most of you know there is a classical question in elementary combinatorics such that if $$a \times b \times c = 180$$ , then how many possible positive integer solution are there for the equation $$?$$

The solution is easy such that $$180=2^2 \times 3^2 \times 5^1$$ and so , for $$a=2^{x_1} \times 3^{y_1} \times 5^{z_1}$$ , $$b=2^{x_2} \times 3^{y_2} \times 5^{z_2}$$ , $$c=2^{x_3} \times 3^{y_3} \times 5^{z_3}$$ .

Then: $$x_1+x_2+x_3=2$$ where $$x_i \geq0$$ , and $$y_1+y_2+y_3=2$$ where $$y_i \geq0$$ and $$z_1+z_2+z_3=1$$ where $$z_i \geq0$$.

So , $$C (4,2) \times C(4,2) \times C(3,1)=108$$.

Everything is clear up to now.However , i thought that how can i find that possible positive integer solutions when the equation is $$a \times b \times c \lt 180$$ instead of $$a \times b \times c = 180$$

After , i started to think about it. Firstly , i thought that if i can calculute the possible solutions for $$x_1+x_2+x_3 \lt2$$ where $$x_i \geq0$$ , and $$y_1+y_2+y_3 \lt 2$$ where $$y_i \geq0$$ and $$z_1+z_2+z_3 \lt1$$ where $$z_i \geq0$$ , then i can find the solution.However , there is a problem such that when i calculate the solution , i do not include the prime numbers and their multiplicites which is in $$180$$.

For example , my solution does not contain $$1 \times 1 \times 179 \lt 180$$

My question is that how can we solve these types of question . Is there any $$\color{blue} {\text{TRICK}}$$ for include all possible ways ? Moreover ,this question can be generalized for $$a \times b \times c \leq 180$$ , then what would happen for it ?

Thanks for helps..

Addendums just added that moderately refine the enumeration of (for example) all positive integer solutions to $$(xyz) \leq 180$$.

The positive integer solutions to $$(xyz) \leq 180$$ can be partitioned into the $$180$$ mutually exclusive sets $$(xyz) = a$$, where $$a \in \{1,2,\dots, 180\}.$$

Then, using the same method that you used in your query, you will examine each value of $$a$$ separately, examining its prime factorization. Although this approach dispenses with any attempt at elegance, the approach is certainly straightforward.

Additions to the answer are provided in sections, Addendum-1, Addendum-2, ... that discuss an alternative approach to the overall problem and then try to connect the two approaches.

The overall problem is:
Enumerate the number of positive integer solutions to $$(xyz) \leq M \in \mathbb{Z^+}$$.

Ideas to note:

• Let $$S_M$$ denote the number of positive integer solutions to $$(xyz) \leq M \in \mathbb{Z^+}$$.

• Let $$T_M$$ denote the number of positive integer solutions to $$(xyz) = M \in \mathbb{Z^+}$$. Then clearly, $$T_M = [S_M - S_{(M-1)}].$$

• The ordered triple $$(a,b,c)$$ will be used to denote the solution $$(x=a, y=b, z=c).$$

• When (for example) computing $$T_{(179)}$$ the solutions $$(1,1,179), (1,179,1),$$ and $$(179,1,1)$$ will not be considered distinct. To prevent overcounting, the constraint of $$x \leq y \leq z$$ will be enforced.

• For $$r \in \mathbb{R}, \lfloor r\rfloor$$ will be used to denote the floor of $$r$$ (i.e. the largest integer $$\leq r)$$.

• The alternative algorithm discards any ideas involving prime factorizations, and therefore supposedly renders the OP's analysis obselete. In fact, the tail end of these addendums will be a (possibly laughable) alternative approach to computing prime factorizations.

Addendum-2 : Computing $$S_{(180)}$$
I think that the clearest demonstration of the alternative approach is to begin with an example. Given the constraint that $$x \leq y \leq z$$, the first consideration is that

$$\left\lfloor \left(\frac{180}{1}\right)^{(1/3)} \right\rfloor = 5.\tag1$$

Therefore, $$x$$ must be an element in $$\{1,2,3,4,5\}.$$ As a further illustration of the algorithm, suppose that you are enumerating all positive integer solutions $$(x,y,z)$$ where $$x=3$$. Consider that

$$\left\lfloor \left(\frac{180}{3}\right)^{(1/2)} \right\rfloor = 7.\tag2$$

Therefore, when $$x=3, y$$ must be an element in $$\{3,4,5,6,7\}.$$ Continuing the illustration of the algorithm, suppose that you are enumerating all positive integer solutions $$(x,y,z)$$ where $$x=3$$ and $$y=5$$. Consider that

$$\left\lfloor \left(\frac{180}{3 \times 5}\right)^{(1/1)} \right\rfloor = 12.\tag3$$

Therefore, when $$x=3$$ and $$y = 5,$$ $$z$$ must be an element in $$\{5,6,7, \cdots, 12\}.$$ There are therefore $$[(12 + 1) - 5] = 8$$ distinct solutions associated with $$x=3$$ and $$y=5$$.

Let $$f_k(M,a) : ~k,M,a \in \mathbb{Z^+}, ~a \leq M~$$ denote :

$$\left\lfloor \left(\frac{M}{a}\right)^{(1/k)} \right\rfloor.$$

Then $$S_{(180)} = \sum_{x=1}^{f_3(180,1)}~ \sum_{y=x}^{f_2(180,x)}~ \sum_{z=y}^{f_1(180,[xy])}~\{1\}$$ $$=~ \sum_{x=1}^{f_3(180,1)}~ \sum_{y=x}^{f_2(180,x)}~\{1 + f_1(180,[xy]) - y\}.\tag4$$

Addendum-3 : Computing $$S_{M}$$
The analysis inherent in equations (1) through (4) of the previous section will be unchanged. Therefore: $$S_{M} ~=~ \sum_{x=1}^{f_3(M,1)}~ \sum_{y=x}^{f_2(M,x)}~\{1 + f_1(M,[xy]) - y\}.\tag5$$

In the original answer, I speculated that employing a computer program on a PC to compute (for example) $$S_{(100,000)}$$ via prime factorizations should run okay. I now speculate that employing a computer program on a PC to compute (for example) $$S_{1,000,000,000}$$ via the alternative algorithm should also be okay.

Further, if $$L$$ is any random number such that $$(10)^{(9)} \leq L < (10)^{(10)}$$, then using a PC to compute $$T_L = S_L - S_{L-1}$$ should also be okay. It is unknown how large $$L$$ can be to allow $$T_L$$ to be readily computable on a modern super computer.

The remainder of the addendums discuss using the computation of $$T_L$$ to determine the prime factorization of $$L$$.

Addendum-4 : Using the enumeration of $$T_{180}$$ to compute the prime factorization of $$(180)$$.

In fact, $$T_{180} = 20$$, rather than $$18$$, as computed by the OP. This is explained as follows.

$$180 = 2^2 \times 3^2 \times 5^1.$$

Setting:
$$X = 2^{x_1} \times 3^{x_2} \times 5^{x_3}$$
$$Y = 2^{y_1} \times 3^{y_2} \times 5^{y_3}$$
$$Z = 2^{z_1} \times 3^{z_2} \times 5^{z_3}$$

and then using Stars and Bars analysis to compute the number of non-negative integer solutions to
$$(x_1 + y_1 + z_1 = 2) ~: \binom{4}{2} = 6.$$
$$(x_2 + y_2 + z_2 = 2) ~: \binom{4}{2} = 6.$$
$$(x_3 + y_3 + z_3 = 1) ~: \binom{3}{1} = 3.$$
Then the initial estimate of $$T_{180}$$ is $$6 \times 6 \times 3 = 108.$$

The second estimate of $$T_{180}$$ as $$\frac{108}{3!} = 18$$ is closer, but also wrong. This second estimate assumes that each solution generated by the previous paragraph occurs $$(3!)$$ times, among the solutions $$(x,y,z)$$. This is wrong, because $$180$$ is divisible by $$4$$ perfect squares, $$\{1,4,9,36\}.$$ Therefore, the initial estimate of 108 solutions must be partitioned into two groups:

The 12 solutions that constitute the 3 permutations each of $$(1,1,180), (2,2,45), (3,3,20), (6,6,5)$$ and the other 96 solutions. These other 96 solutions each involve 3 distinct factors which thus generates (3!) repetitions each.

Therefore, the correct enumeration is $$\frac{96}{3!} + \frac{12}{3} = 20.$$

So the (?? laughable ??) question becomes : how can you use the computation of $$T_{180} = 20$$ to compute the prime factorization of $$(180)$$.

Suppose that $$(180) = (p_1)^{a_1} \times (p_2)^{a_2} \times \cdots (p_r)^{a_r}$$, where
$$p_1, \cdots, p_r$$ are distinct primes in ascending order and $$a_1, \cdots, a_r \in \mathbb{Z^+}$$.

Then you want to enumerate all distinct solutions $$(X,Y,Z)$$, where $$(XYZ) = 180$$, and
$$X$$ has form $$p_1^{x_1} \times \cdots \times p_r^{x_r}$$
$$Y$$ has form $$p_1^{y_1} \times \cdots \times p_r^{y_r}$$
$$Z$$ has form $$p_1^{z_1} \times \cdots \times p_r^{z_r}.$$

The first thing to do is compute the number of distinct solutions to $$S_1 : x_1 + y_1 + z_1 = a_1 : \binom{a_1 + [3-1]}{3-1} = \binom{a_1 + 2}{2}$$ $$S_2 : x_2 + y_2 + z_2 = a_2 : \binom{a_2 + [3-1]}{3-1} = \binom{a_2 + 2}{2}$$ $$~~~\cdots~~~$$ $$S_r : x_r + y_r + z_r = a_r : \binom{a_r + [3-1]}{3-1} = \binom{a_r + 2}{2}.$$

Then, you must compute the number of solutions to $$(xyz) = (180)$$ where all three numbers are the same : $$[0]$$, and the number of solutions to $$(xyz) = (180)$$ where two of the three numbers are the same $$[4]$$.

Further, since $$180 < (2 \times 3 \times 5 \times 7)$$, you know immediately that $$r < 4.$$ Therefore, you have the following constraints:

• $$r \in \{1,2,3\}.$$
• $$S_1 \times \cdots \times S_r = [(3!)d + (3)e]$$ where $$e = 4,$$ and
$$d + e = T_{180} = 20 \implies d = 16 \implies$$
$$(S_1 \times \cdots \times S_r) = [(3!)(16) + (3)(4) = 108].$$

At this point, you are looking for no more than 3 factors $$S_1, \cdots, S_r$$ such that $$S_1 \times \cdots \times S_r = 108$$ and $$S_1, \cdots, S_r$$ are (not necessarily distinct) elements from

$$\left\{\binom{1 + 2}{2} = 3, \binom{2 + 2}{2} = 6, \binom{3 + 2}{2} = 10, \cdots\right\}.$$

Since the whole point of illustrating this section is to facilitate computing the prime factorization of $$L$$, for a very large $$L$$, when $$T_L$$ is known, this is a reasonable stopping point for this section.

Addendum-5 : Using the enumeration of $$T_{L}$$ to compute the prime factorization of $$L$$, for very large $$L$$.

This is a convenient place to emphasize that my understanding of Number Theory is at the undergraduate level (e.g. my involvement with quadratic reciprocity has cobwebs on it), and (for example) I have zero knowledge of computer resources needed to compute all primes less than (large) $$L$$.

For all I know, all of the ideas that I will mention in this section have already been considered.

First of all, for large $$n$$,

$$n ~\text{is prime}~ \iff T_n = 1.$$

Next, instead of defining $$S_n =$$ the number of distinct positive integer solutions to $$(xyz) \leq n$$ you could define it to be $${}_3S_n$$. Similarly, you could redefine $$T_n$$ as $${}_3T_n.$$ This suggests (perhaps wrongly) that for (relevantly) large $$L$$, it might be both feasible and helpful to compute (for example)

$$\{{}_{(10)}T_L, {}_9T_L, \cdots {}_2T_L\}.$$

I have glossed over a point that may be critical:
for large $$L$$, for $$n,m \in \{1,2,\cdots, 10\} ~: m \leq n,$$ it is unclear how feasible it will be to compute how many (non-distinct) solutions to $$(f_1 \times \cdots \times f_n) = L$$ will have exactly $$m$$ identical factors.

• what if it were very large number , would i examine each of them separately ? Jan 26, 2021 at 12:24
• @Bulbasaur When you are dealing with a very large number, assuming that you want an exact enumeration, and assuming that no one discovers a more elegant approach, then yes, you would take the same approach. Note that it should be fairly straightforward to write a computer program (e.g. in Java or C) to [1] identify all prime numbers less than or equal to [M], [2] compute the prime factorization of each separate $a \in \{1,2,\cdots, M\}$, and [3] then apply your combinatorics analysis to each separate value of $a$. For any $M \leq 100,000$, (for example), the computer pgm should run ok. Jan 26, 2021 at 12:29
• thanks for your effort , i appreciate you.$+1$ for this elegant but long explanation.However , i want to wait for seeing whether or not there is any brillant shortcut.Thanks for your time and effort again.. Jan 27, 2021 at 17:12

We can start with listing all the factors of $$180$$ so we have

$$x,y,z|180: x\land y\land z\in\big\{ 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30,36,45,60,90, 180 \big\}$$

We cannot use such as $$(x,y,z)\in\big\{(180,1,1),\space (90,2,1)\big\}$$ because $$x\cdot y\cdot z<180$$ but we can us such as $$\space (x,y,z)=(90,1,1)\space$$ because $$\space 90 \cdot 1\cdot 1 < 180.\space$$ Likewise

$$(60\cdot 3\cdot 1)= 180\implies\\(60\cdot 1\cdot 1) < (60\cdot 2\cdot 1)< 180$$

$$(45\cdot 4\cdot 1)= 180\implies\\(45\cdot 1\cdot 1) < (45\cdot 2\cdot 1)<(45\cdot 3\cdot 1)< 180$$

$$(36\cdot 5\cdot 1)= 180\quad \implies\\ (36\cdot 1\cdot 1) < (36\cdot 2\cdot 1)<(36\cdot 3\cdot 1)<(36\cdot 4\cdot 1)< 180\\ \land \quad (36\cdot 2\cdot 2)<180$$

$$(30\cdot 6\cdot 1) = 180\quad \implies\\ (30\cdot 1\cdot 1) < (30\cdot 2\cdot 1)<(30\cdot 3\cdot 1)<(30\cdot 4\cdot 1)< (30\cdot 5\cdot 1< 180\\ \land \quad (30\cdot 2\cdot 2)<180$$

$$(20\cdot 9\cdot 1) = 180\quad \implies\\ (20\cdot 1\cdot 1) < (20\cdot 2\cdot 1)<(20\cdot 3\cdot 1)<(20\cdot 4\cdot 1)\\< (20\cdot 5\cdot 1< 180 <(20\cdot 6\cdot 1)< (20\cdot 7\cdot 1<(20\cdot 8\cdot 1) < 180\\ \land \quad (20\cdot 2\cdot 2)<(20\cdot 3\cdot 2)< (20\cdot 4\cdot 2)<180$$

If we continue this process through $$x=1$$, we will have all of the combinations and $$\frac16$$ of the permutations of $$x,y,z$$ that satisfy the equation.