[puzzle] another little problem
10-06-2017, 09:03 PM
Post: #1
 pier4r Senior Member Posts: 2,016 Joined: Nov 2014
[puzzle] another little problem lcd: least common multiple.

Wikis are great, Contribute :)
10-07-2017, 07:15 PM (This post was last modified: 10-07-2017 07:32 PM by Thomas Okken.)
Post: #2
 Thomas Okken Senior Member Posts: 865 Joined: Feb 2014
RE: [puzzle] another little problem
(10-06-2017 09:03 PM)pier4r Wrote: lcd: least common multiple.

The prime factorization of 50! contains all the primes up to 50, of which there are 15; the prime factorization of 5! contains the primes up to 5, of which there are 3.

Since GCD(x, y) * LCM(x, y) = x * y, we're looking for pairs of divisors a, b of 5! * 50! such that a * b = 50! * 5! and GCD(a, b) = 5!.

One factor must contain 2^3 * 3 * 5 and the other all the other powers of 2, 3, and 5, because that's the only way for GCD(a, b) to be 5!. All the other 12 prime factors can go with either a or b, but all the occurrences of any prime factor must either all go with a or all with b, since otherwise they'd contribute to the GCD. So, 12 primes to be placed with 2 different factors, that's 2^12 = 4096 possibilities.

EDIT:

No, that's wrong, the 2^3, 3^1, and 5^1 do not have to all be with the same factor; what's important is that one factor has 2^3 and the other has 2^47; one factor has 3^1 while the other has 3^22, and one factor has 5^1 while the other has 5^12. So, four times as many possibilities as I first figured, for a total of 16384.
10-09-2017, 03:03 AM (This post was last modified: 10-09-2017 03:04 AM by AlexFekken.)
Post: #3
 AlexFekken Member Posts: 151 Joined: May 2016
RE: [puzzle] another little problem
Looks correct me to me.

And in general, if n1 is the number of distinct prime factors that the gcd and lcm have in common with the same exponent, n2 the number that they have in common with a different exponent, and n3 the number in the lcm but not the gcd, then the answer would be:

2^(n2+n3-1) if (n2+n3) > 0
1 if n2=n3=0, i.e. gcd = lcm = x = y

That the gcd and lcm are factorials is irrelevant, but makes it easy to count the prime factors.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)