[puzzle] another little problem

10072017, 07:15 PM
(This post was last modified: 10072017 07:32 PM by Thomas Okken.)
Post: #2




RE: [puzzle] another little problem
(10062017 09:03 PM)pier4r Wrote: 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. 

« Next Oldest  Next Newest »

Messages In This Thread 
[puzzle] another little problem  pier4r  10062017, 09:03 PM
RE: [puzzle] another little problem  Thomas Okken  10072017 07:15 PM
RE: [puzzle] another little problem  AlexFekken  10092017, 03:03 AM

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