5
$\begingroup$

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

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.


Addendum-1 : Overview
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.

$\endgroup$
4
  • 1
    $\begingroup$ what if it were very large number , would i examine each of them separately ? $\endgroup$ Jan 26, 2021 at 12:24
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 26, 2021 at 12:29
  • $\begingroup$ @Bulbasaur Addendums added to my answer. $\endgroup$ Jan 27, 2021 at 11:42
  • $\begingroup$ 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.. $\endgroup$ Jan 27, 2021 at 17:12
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .