Author |
Topic: Least Positive Integer, 20 divisors (Read 8577 times) |
|
codpro880
Junior Member
Teachers strike, students hurt. English...
Gender:
Posts: 89
|
|
Least Positive Integer, 20 divisors
« on: May 31st, 2009, 8:39pm » |
Quote Modify
|
Find the least positive integer that has exactly 20 positive integer divisors. I can't seem to find the correct answer. Any hints?
|
« Last Edit: May 31st, 2009, 8:41pm by codpro880 » |
IP Logged |
You miss 100% of the shots you never take.
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Least Positive Integer, 20 divisors
« Reply #1 on: May 31st, 2009, 10:56pm » |
Quote Modify
|
Hint: If the number is p1^a1*p2^a2*p3^a3*...*pk^ak then 20=(1+a1)*(1+a2)*...*(1+ak) Full Solution: Since 20=2*2*5, The number can have at most 3 prime factors. If it has 1 prime factor, it is at least 2^19 If it has 2 prime factors, its least value is 2^9*3 or 2^4*3^3. If it has three prime factors, it is at least 2^4*3*5. So, the least number with 20 factors is the least of these four, which is 2^4*3*5=240. If you need 20 factors >1 then apply the same procedure on 21.
|
« Last Edit: May 31st, 2009, 10:59pm by Ronno » |
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Least Positive Integer, 20 divisors
« Reply #2 on: Jun 1st, 2009, 5:51pm » |
Quote Modify
|
Now, could u find the smallest positive integers that has exactly 30 positive integer divisors.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Least Positive Integer, 20 divisors
« Reply #3 on: Jun 1st, 2009, 11:12pm » |
Quote Modify
|
720 But why?
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
codpro880
Junior Member
Teachers strike, students hurt. English...
Gender:
Posts: 89
|
|
Re: Least Positive Integer, 20 divisors
« Reply #4 on: Jun 2nd, 2009, 8:05am » |
Quote Modify
|
on Jun 1st, 2009, 11:12pm, Ronno wrote: So it would be 2^4*3^2*5 30=2*3*5, so three prime factors at most We can make thirty different groups with 2^4*3^2*5 (which equals 720) 2 2*2 2*2*2 2*2*2*2 3 3*3 2*3 2*2*3 2*2*2*3 2*2*2*2*3 2*3*3 2*2*3*3 2*2*2*3*3 2*2*2*2*3*3 5 2*5 2*2*5 2*2*2*5 2*2*2*2*5 2*3*5 2*2*3*5 2*2*2*3*5 2*2*2*2*3*5 2*3*3*5 2*2*3*3*5 2*2*2*3*3*5 2*2*2*2*3*3*5 3*5 3*3*5 2*3*5 It took me forever to find this answer...is there an easier way to think about it? Seems like it's really just a combinatorics problem...but I don't know how to define it.
|
|
IP Logged |
You miss 100% of the shots you never take.
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Least Positive Integer, 20 divisors
« Reply #5 on: Jun 2nd, 2009, 9:52pm » |
Quote Modify
|
You don't have to compare so many. Just those which have exactly 20 factors. That is, those for which the product of the powers of the primes plus 1 is 20. So, you factor 20 into 1, 2, 3,... factors and use those factors minus 1 as powers of the primes. Since the number is minimal, give the highest power to 2, the next highest power to 3 and so on.
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Least Positive Integer, 20 divisors
« Reply #6 on: Jun 3rd, 2009, 1:17am » |
Quote Modify
|
on May 31st, 2009, 8:39pm, codpro880 wrote:Find the least positive integer that has exactly 20 positive integer divisors. I had this question on a test a year ago. [quote author=Ronno link=board=riddles_easy;num=1243827582;start=0#3 date=06/01/09 at 23:12:24]720 But why? |
| I was playing around thinking that I could come up with something interesting. The factors of 20 are: 1, 2, 4, 5, 10, 20 The prime factors are: 2 * 2 * 5 The factors of 30 are: 1, 2, 3, 5, 6, 10, 15, 30 The prime factors are: 2 * 3 * 5 Problem #1: (1) 20 = 2 * 10 (2) 20 = 4* 5 (3) 20 = 2 * 2 * 5 (1) exponents are 1 and 9: (29) * (31) = 1536 is the smallest such integer. (2) exponents are 3 and 4: (24) * (33) = 432 is the smallest such integer. (3) exponents are 1,1, and 4: (24) * (31) * (51) = 240 is the smallest such integer. 240 is the smallest integer with exactly 20 positive divisors. (as Ronno stated) Problem #2: (1) 30 = 2 * 15 (2) 30 = 3 * 10 (3) 30 = 5 * 6 (4) 30 = 2 * 3 * 5 (1) exponents are 1 and 14: (214) * (31) = 49152 is the smallest such integer. (2) exponents are 2 and 9: (29) * (32) = 4608 is the smallest such integer. (3) exponents are 4 and 5: (25) * (34) = 2592 is the smallest such integer. (4) exponents are 1, 2, and 4: (24) * (32) * (51) = 720 is the smallest such integer. 720 is the smallest integer with exactly 30 positive divisors. I took ... Prime numbers are: 2, 3, 5, 7, 11, 13, ... I then multiplied by 10, getting... 20, 30, 50, 70, 110, 130, ... In problem #1 we needed to find 20 positive integer divisors. In problem #2 we needed to find 30 positive integer divisors. I continued with 50, 70, etc. But I didn't find anything interesting.
|
« Last Edit: Jun 3rd, 2009, 1:23am by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Least Positive Integer, 20 divisors
« Reply #7 on: Jun 3rd, 2009, 8:39am » |
Quote Modify
|
I don't think you can really hope to find a pattern. For instance, consider numbers with 32 factors. The previous cases would lead us to believe the smallest example is 2 * 3 * 5 * 7 * 11, when in fact 2^3 * 3 * 5 * 7 is smaller.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Least Positive Integer, 20 divisors
« Reply #8 on: Jun 3rd, 2009, 10:17am » |
Quote Modify
|
on Jun 3rd, 2009, 8:39am, Obob wrote:I don't think you can really hope to find a pattern. For instance, consider numbers with 32 factors. The previous cases would lead us to believe the smallest example is 2 * 3 * 5 * 7 * 11, when in fact 2^3 * 3 * 5 * 7 is smaller. |
| I see what you mean. My basis was the prime numbers. I mean, working with prime numbers, and then multiply the prime numbers by 10. 2, 3, 5, 7, 11, 13, ... multiplying by 10 20, 30, 50, 70, .... with 20 factors, we get 240 (being the smallest...) with 30 factors, we get 720 (=3*240) then the next factors are: 50, 70, 110, 130, ... I leave it to you I was hoping to find some exciting pattern.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Least Positive Integer, 20 divisors
« Reply #9 on: Jun 3rd, 2009, 11:29am » |
Quote Modify
|
Ah, I see what you meant. The smallest number with 10*p factors, p >= 5 a prime, must be one of 2^(p-1) * 3^4 * 5 2^(2p - 1) * 3^4 2^(5p-1) * 3 2^(10p-1) corresponding to the factorizations 2 * 5 * p 5 * 2p 2 * 5p 10p of 10p. The smallest one is always 2^(p-1) * 3^4 * 5. So in fact the "real pattern" doesn't start until p is at least 5.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Least Positive Integer, 20 divisors
« Reply #10 on: Jun 4th, 2009, 11:00am » |
Quote Modify
|
So, if p = 5, then 2^(5-1) * 3^4 * 5 = 2^4 * 3^4 * 5 = 6480 (= 3^3 * 240) if p = 7, then 2^(7-1) * 3^4 * 5 = 2^6 * 3^4 * 5 = 25920 (= 2^2 * 3^3 * 240) if p = 11, then 2^(11-1) * 3^4 * 5 = 2^10 * 3^4 * 5 = 414720 (= 2^6 * 3^3 * 240)
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
|