2
$\begingroup$

LCM of three natural numbers =150. How many sets of three numbers are possible?

I know how to do this for two natural numbers.There is also a general formula for that. But for 3 numbers it is posing a problem. Is there a standard method for any n natural numbers?

Please help.

$\endgroup$
2
  • $\begingroup$ Are the numbers required to be different? Is order important? $\endgroup$ – paw88789 Mar 31 '15 at 10:53
  • $\begingroup$ I got the answer as 156. $\endgroup$ – archangel89 Mar 31 '15 at 11:06
1
$\begingroup$

I will assume that the numbers are distinct, and that the order doesn't matter.

If we let D be the set of positive divisors of 150, let S be the set of 3-element subsets of D, and

let $A_i$ for $1\le i\le3$ be the set of 3-element subsets of D not containing a multiple of 2, 3, or 25, respectively,

then $|A_1^c\cap A_2^c\cap A_3^c|=|S|-|A_1|-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|-|A_1\cap A_2\cap A_3|$

$\hspace{1.2 in}=\dbinom{12}{3}-\dbinom{6}{3}-\dbinom{6}{3}-\dbinom{8}{3}+\dbinom{3}{3}+\dbinom{4}{3}+\dbinom{4}{3}-0=133$.

$\endgroup$
6
  • $\begingroup$ Hey, this answer actually has the correct result! :) $\endgroup$ – rogerl Mar 31 '15 at 20:14
  • $\begingroup$ @rogerl Thanks for letting me know - I thought it was right, but wasn't absolutely positive. $\endgroup$ – user84413 Mar 31 '15 at 20:15
  • $\begingroup$ I cheated. I used Mathematica to figure it out. $\endgroup$ – rogerl Mar 31 '15 at 20:16
  • $\begingroup$ @rogerl I don't even know how to figure it out with Mathematica. $\endgroup$ – user84413 Mar 31 '15 at 21:41
  • $\begingroup$ Count[Apply[LCM, Subsets[Divisors[150], {3}], {1}], 150] $\endgroup$ – rogerl Mar 31 '15 at 21:43
0
$\begingroup$

Hint

We are looking for the LCM of $3$ numbers, so consider the prime factorization of $150$:

$$150 = 50*3 = 5^2*2*3$$

Therefore, we have numbers of the form: $$5^x2^y3^z = 150$$

Where $x$, $y$, and $z$ are integers.

We also know that: $ 0 \le x \le 1$, $0 \le y \le 1$, $0 \le z \le 1$

$\endgroup$
1
  • $\begingroup$ You meant $0 \leq x \leq 2$. $\endgroup$ – N. F. Taussig Mar 31 '15 at 11:04
0
$\begingroup$

$$150=2\cdot3\cdot5^2$$

The highest power of $2$ in at least one of the three number has to be $1$

This can be achieved in the following ways: $\{1,0,0\};\{1,1,0\};\{1,1,1\}$

The highest power of $5$ in at least one of the three number has to be $2$

This can be achieved in the following ways: $\{2,0,0\};\{2,1,0\};\{2,1,1\};\{2,2,0\};\{2,2,1\};\{2,2,2\}$

So, the number of possible distinct combinations $3\cdot3\cdot6$

$\endgroup$
8
  • $\begingroup$ For the three number set, if the formula for the highest power is $n(\ge1),$ $$\sum_{r=0}^n (1\sum_{s=0}^r 1)=\dfrac{(n+1)(n+2)}2$$ $\endgroup$ – lab bhattacharjee Mar 31 '15 at 11:08
  • $\begingroup$ Your matching doesn't work - the first component will always be divisible by $150$ if you take the factors in order - there are seven ways of having at least one number divisible by $2$, taking order into account, and $3+6+3+3+3+1=16$ ways of having at least one number divisible by $25$. That gives $7\times 7\times 16$ if order doesn't matter. But there are repetitions included, and it is not so easy using this method to de-duplicate. $\endgroup$ – Mark Bennet Mar 31 '15 at 11:11
  • $\begingroup$ @MarkBennet, By the definition of set, I have assumed unique elements and order does not matter . $\endgroup$ – lab bhattacharjee Mar 31 '15 at 11:14
  • $\begingroup$ But then you have to match the elements to get actual factors, and you have seven patterns from your three sets for $2$. $\endgroup$ – Mark Bennet Mar 31 '15 at 11:15
  • $\begingroup$ @MarkBennet, Have you considered uniqueness? $\endgroup$ – lab bhattacharjee Mar 31 '15 at 11:16

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.