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
$\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$
    – Bulbasaur
    Jan 26 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 at 12:29
  • $\begingroup$ @Bulbasaur Addendums added to my answer. $\endgroup$ Jan 27 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$
    – Bulbasaur
    Jan 27 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$

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.